The connected vertex cover problem in \(k\)-regular graphs

DOI10.1007/s10878-019-00403-3zbMath1420.05148OpenAlexW2923664576WikidataQ128209392 ScholiaQ128209392MaRDI QIDQ2424831

Yuchao Li, Wei Wang, Zishen Yang

Publication date: 25 June 2019

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-019-00403-3

zbMATH Keywords

approximation algorithmconnected vertex cover problem\(k\)-regular graph

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (2)

Algorithms and hardness results for edge total domination problem in graphs ⋮ Algorithms and complexity for a class of combinatorial optimization problems with labelling

Cites Work

• Enumerate and expand: Improved algorithms for connected vertex cover and tree cover
• Connected vertex covers in dense graphs
• Vertex and edge covers with clustering properties: Complexity and algorithms
• PTAS for connected vertex cover in unit disk graphs
• 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
• Complexity and algorithms for the connected vertex cover problem in 4-regular graphs
• Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
• A 2-approximation NC algorithm for connected vertex cover and tree cover
• Enumerate and Expand: New Runtime Bounds for Vertex Cover Variants
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Algorithms and Data Structures
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The connected vertex cover problem in \(k\)-regular graphs