Complexity and Approximation Results for the Connected Vertex Cover Problem
DOI10.1007/978-3-540-74839-7_20zbMath1141.68525MaRDI QIDQ3508568
Jérôme Monnot, Laurent Gourvès, 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 algorithm; planar graphs; bipartite graphs; chordal graphs; APX-complete; Connected vertex cover
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
Related Items
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
