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

DOI10.1016/j.jda.2009.01.005zbMath1214.05162OpenAlexW2009816066MaRDI 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 algorithmplanar graphshypergraphsbipartite graphschordal graphsconnected vertex cover

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (24)

On Distance-d Independent Set and Other Problems in Graphs with “few” Minimal Separators ⋮ The \(k\)-hop connected dominating set problem: hardness and polyhedra ⋮ Boundary classes for graph problems involving non-local properties ⋮ Enumeration and maximum number of minimal connected vertex covers in graphs ⋮ The \(k\)-hop connected dominating set problem: approximation and hardness ⋮ Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity ⋮ The connected critical node problem ⋮ The connected vertex cover problem in \(k\)-regular graphs ⋮ An efficient heuristic algorithm for solving connected vertex cover problem ⋮ Complexity and algorithms for the connected vertex cover problem in 4-regular graphs ⋮ Approximation algorithm for minimum connected 3-path vertex cover ⋮ On the approximate compressibility of connected vertex cover ⋮ Unnamed Item ⋮ Kernelization hardness of connectivity problems in \(d\)-degenerate graphs ⋮ Unnamed Item ⋮ Connected vertex cover for \((sP_1+P_5)\)-free graphs ⋮ Algorithms and complexity for a class of combinatorial optimization problems with labelling ⋮ Reducing graph transversals via edge contractions ⋮ On cycle transversals and their connected variants in the absence of a small linear forest ⋮ The balanced connected subgraph problem ⋮ Nonseparating independent sets of Cartesian product graphs ⋮ A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs ⋮ Extension and its price for the connected vertex cover problem ⋮ Revisiting connected vertex cover: FPT algorithms and lossy kernels

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

This page was built for publication: Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs