Publication | Closed Access
Approximating clique is almost NP-complete
397
Citations
19
References
2002
Year
Unknown Venue
Mathematical ProgrammingEngineeringNetwork AnalysisEducationComputational ComplexityComplexityStructural Graph TheoryExtremal CombinatoricsDiscrete MathematicsCombinatorial OptimizationProbabilistic Graph TheoryApproximation TheoryGraph GComputer ScienceGraph AlgorithmLargest CliqueTheory Of ComputingGraph TheoryTime ComplexityExtremal Graph Theory
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="http://www.w3.org/1999/xlink">></ETX>
| Year | Citations | |
|---|---|---|
Page 1
Page 1