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

DOI10.1016/J.JDA.2009.01.005zbMATH Open1214.05162OpenAlexW2009816066MaRDI QIDQ2266936FDOQ2266936

Authors: Laurent Gourvès, Jérôme Monnot, 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

Recommendations

• Complexity and Approximation Results for the Connected Vertex Cover Problem
• On approximation of the vertex cover problem in hypergraphs
• On approximability of connected path vertex cover
• On the approximability of the vertex cover and related problems
• Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
• Publication:4952635
• \(p\)-edge/vertex-connected vertex cover: parameterized and approximation algorithms
• On the parameterized complexity of vertex cover and edge cover with connectivity constraints
• An approximation algorithm for the partial vertex cover problem in hypergraphs
• Complexity and approximation of the connected set-cover problem

zbMATH Keywords

approximation algorithmchordal graphshypergraphsplanar graphsbipartite graphsconnected vertex cover

Mathematics Subject Classification ID

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

Cites Work

• A threshold of ln n for approximating set cover
• Title not available (Why is that?)
• Optimization, approximation, and complexity classes
• Some APX-completeness results for cubic graphs
• Approximation algorithms for NP-hard problems.
• Graph Classes: A Survey
• Depth-first search and the vertex cover problem
• A partial k-arboretum of graphs with bounded treewidth
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Improved approximations for tour and tree covers
• Complexity of approximating bounded variants of optimization problems
• Approximation algorithms for NP-complete problems on planar graphs
• Non-approximability results for optimization problems on bounded degree instances
• Title not available (Why is that?)
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
• Approximation algorithms and hardness results for labeled connectivity problems
• Bidimensionality: new connections between FPT algorithms and PTASs
• Title not available (Why is that?)
• Algorithms – ESA 2004
• A new multilayered {PCP} and the hardness of hypergraph vertex cover
• Enumerate and Expand: New Runtime Bounds for Vertex Cover Variants
• Approximating the tree and tour covers of a graph
• Complexity of the minimum-length corridor problem
• Local search for the minimum label spanning tree problem with bounded color classes.
• Algorithms and Data Structures
• Enumerate and Expand: Improved Algorithms for Connected Vertex Cover and Tree Cover
• How to Trim an MST: A 2-Approximation Algorithm for Minimum Cost Tree Cover

Cited In (37)

• Connected vertex cover for \((sP_1+P_5)\)-free graphs
• On cycle transversals and their connected variants in the absence of a small linear forest
• Complexity and algorithms for the connected vertex cover problem in 4-regular graphs
• Vertex Cover in Conflict Graphs: Complexity and a Near Optimal Approximation
• Connected Vertex Covers in Dense Graphs
• Extension and its price for the connected vertex cover problem
• Approximation algorithm for minimum connected 3-path vertex cover
• On the approximate compressibility of connected vertex cover
• Connected vertex covers in dense graphs
• Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity
• Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
• Enumeration and maximum number of minimal connected vertex covers in graphs
• Revisiting connected vertex cover: FPT algorithms and lossy kernels
• On distance-\(d\) Independent Set and other problems in graphs with ``few minimal separators
• Approximability of the vertex cover problem in power-law graphs
• Complexity and approximation of the connected set-cover problem
• The connected vertex cover problem in \(k\)-regular graphs
• Boundary classes for graph problems involving non-local properties
• A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs
• Reducing graph transversals via edge contractions
• Polynomial Time Approximation Scheme for Connected Vertex Cover in Unit Disk Graph
• The \(k\)-hop connected dominating set problem: hardness and polyhedra
• Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs
• Title not available (Why is that?)
• Connected vertex cover for \((sP_1+P_5)\)-free graphs
• Complexity and Approximation Results for the Connected Vertex Cover Problem
• Vertex and edge covers with clustering properties: Complexity and algorithms
• Reducing graph transversals via edge contractions
• The connected critical node problem
• Price of connectivity for the vertex cover problem and the dominating set problem: conjectures and investigation of critical graphs
• Nonseparating independent sets of Cartesian product graphs
• Graph problems with obligations
• Solving vertex cover in polynomial time on hyperbolic random graphs
• Eternal connected vertex cover problem in graphs: complexity and algorithms
• Algorithms and complexity for a class of combinatorial optimization problems with labelling
• An efficient heuristic algorithm for solving connected vertex cover problem
• The \(k\)-hop connected dominating set problem: approximation and hardness

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2266936)