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

DOI10.1016/j.ipl.2011.04.009zbMath1260.68304OpenAlexW1968635621MaRDI 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 optimizationapproximation algorithmvertex cover \(P_n\) problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) 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 (42)

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 ⋮ 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 the minimum \(k\)-path connected vertex cover problem in unit disk graphs ⋮ A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion ⋮ Unnamed Item ⋮ A 2-approximation algorithm for the vertex coverP₄problem in cubic graphs ⋮ On the vertex cover \(P_3\) problem parameterized by treewidth ⋮ Approximation Algorithm for the Minimum Connected $$k$$-Path Vertex Cover Problem ⋮ On the weighted \(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 ⋮ Approximation algorithm for minimum weight connected-\(k\)-subgraph cover ⋮ A faster FPT algorithm for 3-path vertex cover ⋮ PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs ⋮ 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 fixed-parameter algorithm for the vertex cover \(P_3\) problem ⋮ Efficient algorithm for the vertex cover \(P_k\) problem on cacti ⋮ 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 ⋮ 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 ⋮ Kernels for packing and covering problems ⋮ A simpler PTAS for connected \(k\)-path vertex cover in homogeneous wireless sensor network ⋮ On a relation between \(k\)-path partition and \(k\)-path vertex cover ⋮ The k-Observer Problem on d-regular Graphs ⋮ Algorithm for online 3-path vertex cover ⋮ Partitioning a graph into small pieces with applications to path transversal ⋮ Approximating Partially Bounded Degree Deletion on Directed Graphs ⋮ The \(k\)-path vertex cover in Cartesian product graphs and complete bipartite graphs ⋮ 3-path vertex cover and dissociation number of hexagonal graphs ⋮ The \(k\)-path vertex cover of rooted product graphs ⋮ Approximation algorithms for hitting subgraphs

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

This page was built for publication: A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem