1992/01/01 by Mark Jerrum · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Heuristics #Clique #Heuristic #Combinatorics #Greedy algorithm #Random graph #Graph #Clique problem #Mathematics #Computer science #Mathematical optimization #Theoretical computer science #Chordal graph
paper · doi:10.1002/rsa.3240030402
openalex publication_date 1992/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/20
Abstract In a random graph on n vertices, the maximum clique is likely to be of size very close to 2 lg n . However, the clique produced by applying the naive “greedy” heuristic to a random graph is unlikely to have size much exceeding lg n . The factor of two separating these estimates motivates the search for more effective heuristics. This article analyzes a heuristic search strategy, the Metropolis process , which is just one step above the greedy one in its level of sophistication. It is shown that the Metropolis process takes super‐polynomial time to locate a clique that is only slightly bigger than that produced by the greedy heuristic.