Complexity and algorithms for the connected vertex cover problem in 4-regular graphs
From MaRDI portal
Publication:1735245
DOI10.1016/j.amc.2016.12.004zbMath1411.05247OpenAlexW2562303421MaRDI QIDQ1735245
Wei Wang, Zishen Yang, Yuchao Li
Publication date: 28 March 2019
Published in: Applied Mathematics and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.amc.2016.12.004
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (9)
Connected power domination in graphs ⋮ The connected vertex cover problem in \(k\)-regular graphs ⋮ An efficient heuristic algorithm for solving connected vertex cover problem ⋮ Hitting subgraphs in \(P_4\)-tidy graphs ⋮ Complexity and computation of connected zero forcing ⋮ Connected vertex cover for \((sP_1+P_5)\)-free graphs ⋮ Layered graphs: applications and algorithms ⋮ Nonseparating independent sets of Cartesian product graphs ⋮ Set-weighted games and their application to the cover problem
Cites Work
- Approximating the tree and tour covers of a graph
- Enumerate and expand: Improved algorithms for connected vertex cover and tree cover
- 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
- Some simplified NP-complete graph problems
- 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
This page was built for publication: Complexity and algorithms for the connected vertex cover problem in 4-regular graphs
