Papers › Randomized heuristic for the maximum clique problem
Randomized heuristic for the maximum clique problem
Shalin Shah
A clique in a graph is a set of vertices that are all directly connected to each other i.e. a complete sub-graph. A clique of the largest size is called a maximum clique. Finding the maximum clique in a graph is an NP-hard problem and it cannot be solved by an approximation algorithm that returns a solution within a constant factor of the optimum. In this work, we present a simple and very fast randomized algorithm for the maximum clique problem. We also provide Java code of the algorithm in our git repository. Results show that the algorithm is able to find reasonably good solutions to some randomly chosen DIMACS benchmark graphs. Rather than aiming for optimality, we aim to find good solutions very fast.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections