Sign in
Back
Approximating maximum clique by removing subgraphs
Journal article   Peer reviewed

Approximating maximum clique by removing subgraphs

Uriel Feige
SIAM Journal on Discrete Mathematics, Vol.18(2), pp.219-225
2004
DOI: https://doi.org/10.1137/S089548010240415X
url
https://doi.org/10.1137/S089548010240415XView
Published (Version of record) Restricted
url
https://ezproxy.weizmann.ac.il/login?url=http://dx.doi.org/10.1137/S089548010240415XView
Published (Version of record) Restricted

Abstract

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)).

Details

Metrics

120 Record Views