Towards optimal lower bounds for clique and chromatic number.
From MaRDI portal
Publication:1874411
DOI10.1016/S0304-3975(02)00535-2zbMath1042.68046MaRDI QIDQ1874411
Lars Engebretsen, Jonas Holmerin
Publication date: 25 May 2003
Published in: Theoretical Computer Science (Search for Journal in Brave)
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (7)
Inapproximability results for equations over finite groups ⋮ A review on algorithms for maximum clique problems ⋮ Longest common subsequence problem for unoriented and cyclic strings ⋮ The 0-1 inverse maximum stable set problem ⋮ More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP ⋮ On the advantage over a random assignment ⋮ Efficient computation of sparse structures
Cites Work
- Approximating maximum independent sets by excluding subgraphs
- A still better performance guarantee for approximate graph coloring
- On the ratio of optimal integral and fractional covers
- Zero knowledge and the chromatic number
- Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Improved non-approximability results
- Proof verification and the hardness of approximation problems
- A threshold of ln n for approximating set cover
- A PCP characterization of NP with optimal amortized query complexity
- Probabilistic checking of proofs
- On the hardness of approximating minimization problems
- Interactive proofs and the hardness of approximating cliques
- A Parallel Repetition Theorem
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Some optimal inapproximability results
- On Unapproximable Versions of $NP$-Complete Problems
- On the hardness of approximating the chromatic number
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Towards optimal lower bounds for clique and chromatic number.
