Kernelization and Parameterized Algorithms for 3-Path Vertex Cover

DOI10.1007/978-3-319-55911-7_47zbMath1423.68360arXiv1608.07022OpenAlexW2963995309MaRDI QIDQ2988857

Shaowei Kou, Mingyu Xiao

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

Mathematics Subject Classification ID

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 (13)

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

This page was built for publication: Kernelization and Parameterized Algorithms for 3-Path Vertex Cover