2004/01/01 by Uriel Feige · 4 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Combinatorics #Mathematics #Clique #Log-log plot #Clique number #Binary logarithm #Clique graph #Graph #Approximation algorithm #Discrete mathematics #Constant (computer programming) #Line graph #Computer science #Graph power
paper · doi:10.1137/s089548010240415x
openalex publication_date 2004/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30
We show an algorithm that finds cliques of size (log n/log log n)2 whenever a graph has a clique of size at least n/(log n)b for an arbitrary constant b. This leads to an algorithm that approximates max clique within a factor of O(n(log log n)2/(log n)3), which matches the best approximation ratio known for the chromatic number. The previously best approximation ratio known for max clique was O(n/(log n)2).