Improved non-approximability results for minimum vertex cover with density constraints

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)

zbMATH Keywords

computational complexityapproximation algorithmsvertex coverexpander graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (10)

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

This page was built for publication: Improved non-approximability results for minimum vertex cover with density constraints