A 2-approximation algorithm for the vertex cover P₄ problem in cubic graphs

DOI10.1080/00207160.2014.881476MaRDI QIDQ2931950zbMATH OpenOpenAlexFDO

Authors Yu-Chao Li, Jianhua Tu

Publication date 28 November 2014

Published in International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/00207160.2014.881476

zbMATH Keywords

approximation algorithmcombinatorial optimizationcubic graphsharp lower and upper boundsvertex cover \(P_{4}\) problem

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• The vertex cover \(P_3\) problem in cubic graphs
• An FPT algorithm for the vertex cover \(P_4\) problem
• Computational complexity of minimum \(P_4\) vertex cover problem for regular and \(K_{1, 4}\)-free graphs
• Efficient algorithm for the vertex cover \(P_k\) problem on cacti
• A factor 2 approximation algorithm for the vertex cover P₃ problem

Cites work

• A factor 2 approximation algorithm for the vertex cover P₃ problem
• A generalization of Nemhauser and Trotter's local optimization theorem
• A primal-dual approximation algorithm for the vertex cover P^3 problem
• Minimum \(k\)-path vertex cover
• On computing the minimum 3-path vertex cover and dissociation number of graphs
• On the k-path vertex cover of some graph products
• On the vertex \(k\)-path cover
• Some simplified NP-complete graph problems
• The vertex cover \(P_3\) problem in cubic graphs

Cited in

(21)

• PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs
• Complexity and algorithms for the connected vertex cover problem in 4-regular graphs
• Efficient algorithm for the vertex cover \(P_k\) problem on cacti
• A factor 2 approximation algorithm for the vertex cover P₃ problem
• Approximation algorithm for minimum connected 3-path vertex cover
• Improved approximation algorithms for path vertex covers in regular graphs
• Approximation algorithms for minimum weight connected 3-path vertex cover
• On partial descriptions of König graphs for odd paths and all their spanning supergraphs
• Algorithm for online 3-path vertex cover
• Computational complexity of minimum \(P_4\) vertex cover problem for regular and \(K_{1, 4}\)-free graphs
• The vertex cover \(P_3\) problem in cubic graphs
• Approximation algorithm for the minimum weight connected k-subgraph cover problem
• Approximation algorithms for minimum (weight) connected k-path vertex cover
• Approximation algorithm for the minimum connected k-path vertex cover problem
• A survey on vertex cover \({P_k}\) problem
• König graphs with respect to the 4-path and its spanning supergraphs
• PTAS for minimum \(k\)-path vertex cover in ball graph
• On the König graphs for a 5-path and its spanning supergraphs
• The weighted k-path vertex cover problem on series-parallel graphs
• A faster FPT algorithm for 3-path vertex cover
• An FPT algorithm for the vertex cover \(P_4\) problem

This page was built for publication: A 2-approximation algorithm for the vertex cover \(P_{4}\) problem in cubic graphs

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