Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs

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

zbMATH Keywords

approximation algorithm; planar graphs; hypergraphs; bipartite graphs; chordal graphs; connected vertex cover

Mathematics Subject Classification ID

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

Kernelization hardness of connectivity problems in \(d\)-degenerate graphs

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