Improved non-approximability results for vertex cover with density constraints

DOI10.1007/3-540-61332-3_167zbMath1529.68200OpenAlexW1818184450MaRDI QIDQ6184678

Andrea E. F. Clementi, Luca Trevisan

Publication date: 29 January 2024

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-61332-3_167

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Density (toughness, etc.) (05C42)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Completeness in approximation classes
• Ramanujan graphs
• The Steiner problem with edge lengths 1 and 2
• Optimization, approximation, and complexity classes
• Some simplified NP-complete graph problems
• Reducibility among Combinatorial Problems
• On approximation properties of the Independent set problem for degree 3 graphs

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