Improved non-approximability results for minimum vertex cover with density constraints
From MaRDI portal
Publication:1960657
DOI10.1016/S0304-3975(97)00226-0zbMath0933.68101MaRDI QIDQ1960657
Andrea E. F. Clementi, Luca Trevisan
Publication date: 12 January 2000
Published in: Theoretical Computer Science (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Complexity of approximating bounded variants of optimization problems ⋮ Approximation hardness of edge dominating set problems ⋮ Models of greedy algorithms for graph problems ⋮ Domination chain: characterisation, classical complexity, parameterised complexity and approximability ⋮ Approximating vertex cover in dense hypergraphs ⋮ Nearly tight approximation bounds for vertex cover on dense \(k\)-uniform \( k\)-partite hypergraphs ⋮ Approximating Edge Dominating Set in Dense Graphs ⋮ On approximating minimum vertex cover for graphs with perfect matching ⋮ On the Complexity Landscape of the Domination Chain ⋮ Approximating edge dominating set in dense graphs
Cites Work
- Completeness in approximation classes
- Expanders, randomness, or time versus space
- Ramanujan graphs
- The Steiner problem with edge lengths 1 and 2
- Explicit constructions of linear-sized superconcentrators
- Optimization, approximation, and complexity classes
- Some simplified NP-complete graph problems
- Derandomized graph products
- Two prover protocols
- Improved non-approximability results
- On the hardness of approximating minimization problems
- On the approximation of shortest common supersequences and longest common subsequences
- Efficient probabilistically checkable proofs and applications to approximations
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
