A fixed-parameter algorithm for the vertex cover P₃ problem
From MaRDI portal
Publication:477591
Recommendations
- Fixed-parameter algorithms for Vertex Cover \(P_3\)
- An FPT algorithm for the vertex cover \(P_4\) problem
- On the vertex cover \(P_3\) problem parameterized by treewidth
- An improved algorithm for the vertex cover \(P_3\) problem on graphs of bounded treewidth
- A faster FPT algorithm for 3-path vertex cover
Cites work
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- A complexity dichotomy for finding disjoint solutions of vertex deletion problems
- A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
- A generalization of Nemhauser and Trotter's local optimization theorem
- 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
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Approximation algorithms for clique-transversal sets and clique-independent sets in cubic graphs
- Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
- Finding odd cycle transversals.
- Fixed-parameter algorithms for cluster vertex deletion
- Graph theory with applications
- Iterative Compression for Exactly Solving NP-Hard Minimization Problems
- Minimum \(k\)-path vertex cover
- Node-Deletion Problems on Bipartite Graphs
- On computing the minimum 3-path vertex cover and dissociation number of graphs
- On the vertex \(k\)-path cover
Cited in
(38)- A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
- An efficient polynomial time approximation scheme for the vertex cover \(P_3\) problem on planar graphs
- Kernelization and Parameterized Algorithms for 3-Path Vertex Cover
- An articulation point-based approximation algorithm for minimum vertex cover problem
- Approximating bounded degree deletion via matroid matching
- Hitting subgraphs in \(P_4\)-tidy graphs
- Faster parameterized algorithm for cluster vertex deletion
- Generating Faster Algorithms for d-Path Vertex Cover
- An improved algorithm for the vertex cover \(P_3\) problem on graphs of bounded treewidth
- An \(O^\ast ( 2 . 61 9^k )\) algorithm for 4-path vertex cover
- Parameterized algorithm for 3-path vertex cover
- Kernels for packing and covering problems
- The vertex cover \(P_3\) problem in cubic graphs
- Approximation algorithm for minimum weight connected-\(k\)-subgraph cover
- Faster parameterized algorithms for two vertex deletion problems
- Faster FPT algorithm for 5-path vertex cover
- An FPT algorithm for the vertex cover \(P_4\) problem
- An efficient local search framework for the minimum weighted vertex cover problem
- A measure and conquer approach for the parameterized bounded degree-one vertex deletion
- A faster FPT algorithm for 3-path vertex cover
- Faster computation of the maximum dissociation set and minimum 3-path vertex cover in graphs
- A \(5k\)-vertex kernel for 3-path vertex cover
- The weighted \(k\)-path vertex cover problem on series-parallel graphs
- The \(k\)-path vertex cover in Cartesian product graphs and complete bipartite graphs
- Computing connected-\(k\)-subgraph cover with connectivity requirement
- Approximation algorithm for minimum connected 3-path vertex cover
- A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
- Algorithm for online 3-path vertex cover
- On the vertex cover \(P_3\) problem parameterized by treewidth
- PTAS for minimum \(k\)-path vertex cover in ball graph
- Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
- A multi-start iterated greedy algorithm for the minimum weight vertex cover \(P_3\) problem
- Approximation algorithms for minimum (weight) connected \(k\)-path vertex cover
- Fixed-parameter algorithms for Vertex Cover \(P_3\)
- PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs
- A parameterized algorithm for bounded-degree vertex deletion
- Approximating partially bounded degree deletion on directed graphs
- Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing}
This page was built for publication: A fixed-parameter 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 Q477591)
