A primal-dual approximation algorithm for the vertex cover \(P^3\) problem

DOI10.1016/j.tcs.2011.09.013zbMath1228.68033OpenAlexW2070576097MaRDI QIDQ650946

Wenli Zhou, Jian-hua Tu

Publication date: 7 December 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.09.013

zbMATH Keywords

primal-dual methodcombinatorial optimizationapproximation algorithmvertex cover \(P_{n}\) problem

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Signed and weighted graphs (05C22)

Related Items (51)

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 ⋮ Polynomial time recognition of vertices contained in all (or no) maximum dissociation sets of a tree ⋮ 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 ⋮ 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 König graphs for a 5-path and its spanning supergraphs ⋮ 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 ⋮ Improved approximation algorithms for hitting 3-vertex paths ⋮ Computing connected-\(k\)-subgraph cover with connectivity requirement ⋮ Analyzing the 3-path vertex cover problem in planar bipartite graphs ⋮ A polynomial-time algorithm of finding a minimum \(k\)-path vertex cover and a maximum \(k\)-path packing in some graphs ⋮ Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs ⋮ Approximation algorithm for minimum weight connected-\(k\)-subgraph cover ⋮ Maximum dissociation sets in subcubic trees ⋮ A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem ⋮ A faster FPT algorithm for 3-path vertex cover ⋮ On the maximum number of maximum dissociation sets in trees with given dissociation number ⋮ An FPT algorithm for the vertex cover \(P_4\) problem ⋮ PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs ⋮ The vertex cover \(P_3\) problem in cubic graphs ⋮ 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 ⋮ The geodesic-transversal problem ⋮ 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 ⋮ 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 ⋮ A PTAS for the minimum weight connected vertex cover \(P_3\) problem on unit disk graphs ⋮ Approximating the discrete time-cost tradeoff problem with bounded depth ⋮ Approximating the discrete time-cost tradeoff problem with bounded depth ⋮ Algorithm for online 3-path vertex cover ⋮ König Graphs with Respect to the 4-Path and Its Spanning Supergraphs ⋮ Approximating Partially Bounded Degree Deletion on Directed Graphs ⋮ The \(k\)-path vertex cover in Cartesian product graphs and complete bipartite graphs ⋮ 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 ⋮ On partial descriptions of König graphs for odd paths and all their spanning supergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• New primal-dual algorithms for Steiner tree problems
• 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
• A primal-dual approximation algorithm for generalized Steiner network problems
• Minimum \(k\)-path vertex cover
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• The importance of being biased
• 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
• A General Approximation Technique for Constrained Forest Problems

This page was built for publication: A primal-dual approximation algorithm for the vertex cover \(P^3\) problem