The vertex cover P₃ problem in cubic graphs

DOI10.1016/J.IPL.2013.04.002MaRDI QIDQ2444740zbMATH OpenOpenAlexFDO

Authors Jianhua Tu, Fengmei 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

approximation algorithmcombinatorial optimizationcubic graphvertex cover \(P_3\) problem

Mathematics Subject Classification ID

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

Recommendations

• A 2-approximation algorithm for the vertex cover \(P_{4}\) problem in cubic graphs
• A fixed-parameter algorithm for the vertex cover P₃ problem
• 3-path vertex cover and dissociation number of hexagonal graphs
• Minimum \(k\)-path vertex cover
• A primal-dual approximation algorithm for the vertex cover P^3 problem

Cites work

• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• A factor 2 approximation algorithm for the vertex cover P₃ problem
• A linear-time approximation algorithm for the weighted vertex cover problem
• A primal-dual approximation algorithm for the vertex cover P^3 problem
• A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
• Approximation algorithms for clique-transversal sets and clique-independent sets in cubic graphs
• Graph theory with applications
• Minimum \(k\)-path vertex cover
• On computing the minimum 3-path vertex cover and dissociation number of graphs
• On the vertex \(k\)-path cover
• Some simplified NP-complete graph problems

Cited in

(35)

• An efficient polynomial time approximation scheme for the vertex cover \(P_3\) problem on planar graphs
• PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs
• Efficient algorithm for the vertex cover \(P_k\) problem on cacti
• Fixed-parameter algorithms for Vertex Cover \(P_3\)
• 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
• Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs
• The geodesic-transversal problem
• 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 \(k\)-path vertex cover of rooted product 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
• Approximation algorithms for minimum (weight) connected k-path vertex cover
• Kernelization of the 3-path vertex cover problem
• A 2-approximation algorithm for the vertex cover \(P_{4}\) problem in cubic graphs
• scientific article; zbMATH DE number 6390842 (Why is no real title available?)
• Approximation algorithm for the minimum connected k-path vertex cover problem
• On complexity of total vertex cover on subcubic graphs
• scientific article; zbMATH DE number 426156 (Why is no real title available?)
• Recouvrement et partition en chaînes des arêtes d'un graphe cubique
• A survey on vertex cover \({P_k}\) 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
• Approximating partially bounded degree deletion on directed graphs
• Approximating bounded degree deletion via matroid matching
• 3-path vertex cover and dissociation number of hexagonal graphs
• 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
• A primal-dual approximation algorithm for the vertex cover P^3 problem
• Cluster vertex deletion problems on cubic graphs
• Analyzing the 3-path vertex cover problem in selected graph classes
• A faster FPT algorithm for 3-path vertex cover

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

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