Kernelization and Parameterized Algorithms for 3-Path Vertex Cover
From MaRDI portal
Publication:2988857
DOI10.1007/978-3-319-55911-7_47zbMath1423.68360arXiv1608.07022OpenAlexW2963995309MaRDI QIDQ2988857
Publication date: 19 May 2017
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1608.07022
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Moderately exponential time algorithms for the maximum bounded-degree-1 set problem, Unnamed Item, An \(O^\ast ( 2 . 61 9^k )\) algorithm for \textsc{4-path vertex cover}, A \(5k\)-vertex kernel for 3-path vertex cover, Unnamed Item, Faster parameterized algorithms for two vertex deletion problems, Kernels for packing and covering problems, Unnamed Item, Faster parameterized algorithm for cluster vertex deletion, Algorithm for online 3-path vertex cover, Parameterized algorithm for 3-path vertex cover, Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing}, A \(5k\)-vertex kernel for \(P_2\)-packing
Cites Work
- Unnamed Item
- On a generalization of Nemhauser and Trotter's local optimization theorem
- A fixed-parameter algorithm for the vertex cover \(P_3\) problem
- Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
- Exact exponential algorithms.
- On computing the minimum 3-path vertex cover and dissociation number of graphs
- A generalization of Nemhauser and Trotter's local optimization theorem
- Looking at the stars
- A parameterized perspective on packing paths of length two
- An optimal parallel solution for the path cover problem on \(P_{4}\)-sparse graphs
- A faster FPT algorithm for 3-path vertex cover
- An improved kernelization for \(P_{2}\)-packing
- Some results on graphs without long induced paths
- Fixed-parameter algorithms for Vertex Cover \(P_3\)
- Minimum \(k\)-path vertex cover
- The complexity of dissociation set problems in graphs
- On the vertex \(k\)-path cover
- Finding a minimum path cover of a distance-hereditary graph in polynomial time
- NP-hard graph problems and boundary classes of graphs
- Independent packings in structured graphs
- A Parameterized Algorithm for Bounded-Degree Vertex Deletion
- Kernels for Packing and Covering Problems
- A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion
- On F-independence in graphs
- Node-Deletion Problems on Bipartite Graphs
- The complexity of restricted spanning tree problems
