The vertex cover \(P_3\) problem in cubic graphs

DOI10.1016/j.ipl.2013.04.002zbMath1358.05234OpenAlexW2007945292MaRDI QIDQ2444740

Jian-hua Tu, Feng-mei Yang

Publication date: 11 April 2014

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2013.04.002

zbMATH Keywords

combinatorial optimizationapproximation algorithmcubic graphvertex cover \(P_3\) problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) 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 (25)

Approximation algorithms for minimum (weight) connected \(k\)-path vertex cover ⋮ Kernelization of the 3-path vertex cover problem ⋮ Approximating Bounded Degree Deletion via Matroid Matching ⋮ An efficient polynomial time approximation scheme for the vertex cover \(P_3\) problem on planar graphs ⋮ A 2-approximation algorithm for the vertex coverP₄problem in cubic graphs ⋮ Approximation Algorithm for the Minimum Connected $$k$$-Path Vertex Cover Problem ⋮ The k‐path vertex cover: General bounds and chordal graphs ⋮ Computing connected-\(k\)-subgraph cover with connectivity requirement ⋮ Analyzing the 3-path vertex cover problem in planar bipartite graphs ⋮ Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs ⋮ A faster FPT algorithm for 3-path vertex cover ⋮ PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs ⋮ Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization ⋮ Approximation algorithm for the minimum weight connected \(k\)-subgraph cover problem ⋮ On the complexity of making a distinguished vertex minimum or maximum degree by vertex deletion ⋮ PTAS for minimum \(k\)-path vertex cover in ball graph ⋮ The geodesic-transversal 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 ⋮ Algorithm for online 3-path vertex cover ⋮ Approximating Partially Bounded Degree Deletion on Directed Graphs ⋮ Computational complexity of minimum \(P_4\) vertex cover problem for regular and \(K_{1, 4}\)-free graphs ⋮ 3-path vertex cover and dissociation number of hexagonal graphs ⋮ The \(k\)-path vertex cover of rooted product graphs

Cites Work

• Unnamed Item
• 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
• Some simplified NP-complete graph problems
• A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
• A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
• Approximation algorithms for clique-transversal sets and clique-independent sets in cubic graphs
• Minimum \(k\)-path vertex cover
• On the vertex \(k\)-path cover
• A linear-time approximation algorithm for the weighted vertex cover problem
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem

This page was built for publication: The vertex cover \(P_3\) problem in cubic graphs