Complexity and Approximation Results for the Connected Vertex Cover Problem
DOI10.1007/978-3-540-74839-7_20zbMath1141.68525OpenAlexW1629870200MaRDI QIDQ3508568
Laurent Gourvès, Jérôme Monnot, Bruno Escoffier
Publication date: 1 July 2008
Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-74839-7_20
approximation algorithmplanar graphsbipartite graphschordal graphsAPX-completeConnected vertex cover
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) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (4)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximating the tree and tour covers of a graph
- Vertex and edge covers with clustering properties: Complexity and algorithms
- On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
- Depth-first search and the vertex cover problem
- A partial k-arboretum of graphs with bounded treewidth
- Some APX-completeness results for cubic graphs
- Improved approximations for tour and tree covers
- Enumerate and Expand: Improved Algorithms for Connected Vertex Cover and Tree Cover
- Enumerate and Expand: New Runtime Bounds for Vertex Cover Variants
- How to Trim an MST: A 2-Approximation Algorithm for Minimum Cost Tree Cover
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- Graph Classes: A Survey
- Approximation algorithms for NP-complete problems on planar graphs
- Algorithms and Data Structures
This page was built for publication: Complexity and Approximation Results for the Connected Vertex Cover Problem
