A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem

DOI10.1016/j.ipl.2011.04.009zbMath1260.68304MaRDI QIDQ1944113

Wenli Zhou, Jian-hua Tu

Publication date: 4 April 2013

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

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

zbMATH Keywords

combinatorial optimization; approximation algorithm; vertex cover \(P_n\) problem

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

90C27: Combinatorial optimization

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

Related Items

Unnamed Item, The k-Observer Problem on d-regular Graphs, 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, Approximation algorithms for minimum (weight) connected \(k\)-path vertex cover, Kernelization of the 3-path vertex cover problem, On the weighted \(k\)-path vertex cover problem, A fixed-parameter algorithm for the vertex cover \(P_3\) problem, PTAS for minimum \(k\)-path vertex cover in ball graph, Approximate association via dissociation, A PTAS for minimum weighted connected vertex cover \(P_3\) problem in 3-dimensional wireless sensor networks, A simpler PTAS for connected \(k\)-path vertex cover in homogeneous wireless sensor network, A faster FPT algorithm for 3-path vertex cover, Moderately exponential time algorithms for the maximum bounded-degree-1 set problem, 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, Approximation algorithms for minimum weight connected 3-path vertex cover, A multi-start iterated greedy algorithm for the minimum weight vertex cover \(P_3\) problem, On a relation between \(k\)-path partition and \(k\)-path vertex cover, Approximation algorithms for hitting subgraphs, Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs, Approximation algorithm for minimum weight connected-\(k\)-subgraph cover, Kernels for packing and covering problems, Algorithm for online 3-path vertex cover, Partitioning a graph into small pieces with applications to path transversal, The \(k\)-path vertex cover in Cartesian product graphs and complete bipartite graphs, The \(k\)-path vertex cover of rooted product graphs, PTAS for the minimum \(k\)-path connected vertex cover problem in unit disk graphs, On the vertex cover \(P_3\) problem parameterized by treewidth, The vertex cover \(P_3\) problem in cubic graphs, On the vertex \(k\)-path cover, Approximation algorithm for the minimum weight connected \(k\)-subgraph cover problem, A 2-approximation algorithm for the vertex coverP₄problem in cubic graphs, Approximation Algorithm for the Minimum Connected $$k$$-Path Vertex Cover Problem, A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion

Cites Work

• Unnamed Item
• 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
• Primal-dual approximation algorithms for feedback problems in planar graphs
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• A linear-time approximation algorithm for the weighted vertex cover problem
• Approximating Minimum Subset Feedback Sets in Undirected Graphs with Applications
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem