A factor 2 approximation algorithm for the vertex cover P₃ problem

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

Title not available (Why is that?)
Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
A primal-dual approximation algorithm for the vertex cover $P^3$ problem
Primal-dual approximation algorithms for feedback problems in planar graphs
A linear-time approximation algorithm for the weighted vertex cover problem
Approximating Minimum Subset Feedback Sets in Undirected Graphs with Applications

Cited In (44)

An efficient polynomial time approximation scheme for the vertex cover $P_3$ problem on planar graphs
Partitioning a graph into small pieces with applications to path transversal
Approximation algorithms for minimum (weight) connected $k$-path vertex cover
Fixed-parameter algorithms for Vertex Cover $P_3$
On the weighted $k$-path vertex cover problem
Approximating Partially Bounded Degree Deletion on Directed Graphs
A fixed-parameter algorithm for the vertex cover $P_3$ problem
On the vertex cover $P_3$ problem parameterized by treewidth
A primal-dual approximation algorithm for the vertex cover $P^3$ problem
Efficient algorithm for the vertex cover $P_k$ problem on cacti
Approximation algorithms for hitting subgraphs
Computing connected-$k$-subgraph cover with connectivity requirement
Approximation algorithm for minimum connected 3-path vertex cover
Approximation algorithms for minimum weight connected 3-path vertex cover
Kernelization of the 3-path vertex cover problem
The $k$-path vertex cover of rooted product graphs
A multi-start iterated greedy algorithm for the minimum weight vertex cover $P_3$ problem
3-path vertex cover and dissociation number of hexagonal graphs
Moderately exponential time algorithms for the maximum bounded-degree-1 set problem
Approximation algorithm for minimum weight connected-$k$-subgraph cover
A simpler PTAS for connected $k$-path vertex cover in homogeneous wireless sensor network
The $k$-path vertex cover in Cartesian product graphs and complete bipartite graphs
A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion
On a relation between $k$-path partition and $k$-path vertex cover
Approximation algorithm and FPT algorithm for connected-$k$-subgraph cover on minor-free graphs
Approximation Algorithm for the Minimum Connected $$k$$-Path Vertex Cover Problem
PTAS for the minimum $k$-path connected vertex cover problem in unit disk graphs
Approximation algorithm for the minimum weight connected $k$-subgraph cover problem
On the vertex $k$-path cover
The vertex cover $P_3$ problem in cubic graphs
A 2-approximation algorithm for the vertex coverP₄problem in cubic graphs
PTAS for minimum $k$-path vertex cover in ball graph
Approximate association via dissociation
Algorithm for online 3-path vertex cover
The k-Observer Problem on d-regular Graphs
A PTAS for minimum weighted connected vertex cover $P_3$ problem in 3-dimensional wireless sensor networks
PTAS for $\mathcal{H}$-free node deletion problems in disk graphs
Analyzing the 3-path vertex cover problem in planar bipartite graphs
Kernels for packing and covering problems
A faster FPT algorithm for 3-path vertex cover
Title not available (Why is that?)
The k‐path vertex cover: General bounds and chordal graphs
Approximating Bounded Degree Deletion via Matroid Matching
Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs

Recommendations

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

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