Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
From MaRDI portal
Publication:2266936
DOI10.1016/j.jda.2009.01.005zbMath1214.05162MaRDI QIDQ2266936
Jérôme Monnot, Laurent Gourvès, Bruno Escoffier
Publication date: 26 February 2010
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jda.2009.01.005
approximation algorithm; planar graphs; hypergraphs; bipartite graphs; chordal graphs; connected vertex cover
05C10: Planar graphs; geometric and topological aspects of graph theory
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
Related Items
The \(k\)-hop connected dominating set problem: hardness and polyhedra, Kernelization hardness of connectivity problems in \(d\)-degenerate graphs, On Distance-d Independent Set and Other Problems in Graphs with “few” Minimal Separators
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximating the tree and tour covers of a graph
- Complexity of the minimum-length corridor problem
- 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
- Optimization, approximation, and complexity classes
- A partial k-arboretum of graphs with bounded treewidth
- Some APX-completeness results for cubic graphs
- Local search for the minimum label spanning tree problem with bounded color classes.
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Improved approximations for tour and tree covers
- Complexity of approximating bounded variants of optimization problems
- Approximation algorithms and hardness results for labeled connectivity problems
- A threshold of ln n for approximating set cover
- Enumerate and Expand: Improved Algorithms for Connected Vertex Cover and Tree Cover
- A new multilayered PCP and the hardness of hypergraph vertex 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
- Non-approximability results for optimization problems on bounded degree instances
- Algorithms and Data Structures
- Algorithms – ESA 2004
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph