A 2-approximation algorithm for the vertex coverP4problem in cubic graphs

DOI10.1080/00207160.2014.881476zbMath1303.05199OpenAlexW2069827532MaRDI QIDQ2931950

Yuchao Li, Jian-hua 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

combinatorial optimizationapproximation algorithmcubic graphsharp lower and upper boundsvertex cover \(P_{4}\) problem

Mathematics Subject Classification ID

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

Related Items

Approximation algorithms for minimum (weight) connected \(k\)-path vertex cover ⋮ Unnamed Item ⋮ On the König graphs for a 5-path and its spanning supergraphs ⋮ Approximation Algorithm for the Minimum Connected $$k$$-Path Vertex Cover Problem ⋮ A faster FPT algorithm for 3-path vertex cover ⋮ An FPT algorithm for the vertex cover \(P_4\) problem ⋮ PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs ⋮ Approximation algorithm for the minimum weight connected \(k\)-subgraph cover problem ⋮ PTAS for minimum \(k\)-path vertex cover in ball graph ⋮ Approximation algorithm for minimum connected 3-path vertex cover ⋮ Approximation algorithms for minimum weight connected 3-path vertex cover ⋮ Algorithm for online 3-path vertex cover ⋮ König Graphs with Respect to the 4-Path and Its Spanning Supergraphs ⋮ On partial descriptions of König graphs for odd paths and all their spanning supergraphs

Cites Work

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

This page was built for publication: A 2-approximation algorithm for the vertex coverP₄problem in cubic graphs