A fixed-parameter algorithm for the vertex cover \(P_3\) problem
From MaRDI portal
Publication:477591
DOI10.1016/j.ipl.2014.06.018zbMath1305.05223MaRDI QIDQ477591
Publication date: 9 December 2014
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2014.06.018
Related Items
Unnamed Item, An Articulation Point-Based Approximation Algorithm for Minimum Vertex Cover Problem, Unnamed Item, Approximating Partially Bounded Degree Deletion on Directed Graphs, Approximating Bounded Degree Deletion via Matroid Matching, A \(5k\)-vertex kernel for 3-path vertex cover, Computing connected-\(k\)-subgraph cover with connectivity requirement, Approximation algorithms for minimum (weight) connected \(k\)-path vertex cover, 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 faster FPT algorithm for 3-path vertex cover, 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, Fixed-parameter algorithms for Vertex Cover \(P_3\), Approximation algorithm for minimum connected 3-path vertex cover, A multi-start iterated greedy algorithm for the minimum weight vertex cover \(P_3\) problem, Faster parameterized algorithm for cluster vertex deletion, Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing}, Approximation algorithm for minimum weight connected-\(k\)-subgraph cover, Kernels for packing and covering problems, An efficient local search framework for the minimum weighted vertex cover problem, Algorithm for online 3-path vertex cover, Parameterized algorithm for 3-path vertex cover, The \(k\)-path vertex cover in Cartesian product graphs and complete bipartite graphs, On the vertex cover \(P_3\) problem parameterized by treewidth, An \(O^\ast ( 2 . 61 9^k )\) algorithm for \textsc{4-path vertex cover}, Faster parameterized algorithms for two vertex deletion problems, A Parameterized Algorithm for Bounded-Degree Vertex Deletion, Kernelization and Parameterized Algorithms for 3-Path Vertex Cover, A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion, Faster Computation of the Maximum Dissociation Set and Minimum 3-Path Vertex Cover in Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On computing the minimum 3-path vertex cover and dissociation number of graphs
- A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
- A generalization of Nemhauser and Trotter's local optimization theorem
- Finding odd cycle transversals.
- Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
- Fixed-parameter algorithms for cluster vertex deletion
- A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
- A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
- Approximation algorithms for clique-transversal sets and clique-independent sets in cubic graphs
- Minimum \(k\)-path vertex cover
- On the vertex \(k\)-path cover
- Iterative Compression for Exactly Solving NP-Hard Minimization Problems
- A linear-time approximation algorithm for the weighted vertex cover problem
- Node-Deletion Problems on Bipartite Graphs
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems
