The computational complexity of approximating omega (G), the size of the largest clique in a graph G, within a given factor is considered. It is shown that if certain approximation procedures exist, then EXPTIME=NEXPTIME and NP=P.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="htt...
Highlights, strengths & weaknesses, commercial applications, and societal impact — written for this paper on demand.
No comments yet
Be the first to share your thoughts!