Connected vertex covers in dense graphs

DOI10.1016/j.tcs.2010.03.021zbMath1207.68229OpenAlexW2050461440MaRDI QIDQ974753

Eythan Levy, Jean Cardinal

Publication date: 7 June 2010

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.03.021

zbMATH Keywords

approximation algorithmvertex coverconnected vertex coverdense graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25)

Related Items (16)

Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity ⋮ The Price of Connectivity for Cycle Transversals ⋮ Extension of some edge graph problems: standard, parameterized and approximation complexity ⋮ The price of connectivity for dominating set: upper bounds and complexity ⋮ The connected vertex cover problem in \(k\)-regular graphs ⋮ On the price of independence for vertex cover, feedback vertex set and odd cycle transversal ⋮ Unnamed Item ⋮ Price of connectivity for the vertex cover problem and the dominating set problem: conjectures and investigation of critical graphs ⋮ The price of connectivity for feedback vertex set ⋮ Approximation algorithm for minimum connected 3-path vertex cover ⋮ 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 ⋮ The price of connectivity for cycle transversals ⋮ Approximating edge dominating set in dense graphs ⋮ Extension and its price for the connected vertex cover problem ⋮ Approximating Subdense Instances of Covering Problems

Uses Software

• GraPHedron

Cites Work

• Unnamed Item
• Unnamed Item
• Enumerate and expand: Improved algorithms for connected vertex cover and tree cover
• Facet defining inequalities among graph invariants: The system graphedron
• Depth-first search and the vertex cover problem
• Approximating the dense set-cover problem
• An approximation of the minimum vertex cover in a graph
• A 2-approximation NC algorithm for connected vertex cover and tree cover
• Parameterized complexity of Vertex Cover variants
• Complexity and Approximation Results for the Connected Vertex Cover Problem
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Improved Approximation Bounds for Edge Dominating Set in Dense Graphs
• Computing and Combinatorics
• Polynomial time approximation schemes for some dense instances of NP-hard optimization problems

This page was built for publication: Connected vertex covers in dense graphs