A faster FPT algorithm for 3-path vertex cover

DOI10.1016/j.ipl.2015.12.002zbMath1347.68182OpenAlexW2199703934MaRDI QIDQ903365

Ján Katrenič

Publication date: 5 January 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/10976/

zbMATH Keywords

computational complexityanalysis of algorithmsgraph algorithmsfixed-parameter algorithmbranch and reducedissociation numberpath vertex cover

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (27)

Polynomial time recognition of vertices contained in all (or no) maximum dissociation sets of a tree ⋮ An efficient polynomial time approximation scheme for the vertex cover \(P_3\) problem on planar graphs ⋮ Unnamed Item ⋮ An \(O^\ast ( 2 . 61 9^k )\) algorithm for \textsc{4-path vertex cover} ⋮ On the vertex cover \(P_3\) problem parameterized by treewidth ⋮ A \(5k\)-vertex kernel for 3-path vertex cover ⋮ Computing connected-\(k\)-subgraph cover with connectivity requirement ⋮ Approximation algorithm for minimum weight connected-\(k\)-subgraph cover ⋮ Maximum dissociation sets in subcubic trees ⋮ On the maximum number of maximum dissociation sets in trees with given dissociation number ⋮ Faster parameterized algorithms for two vertex deletion problems ⋮ Kernelization and Parameterized Algorithms for 3-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 ⋮ The geodesic-transversal problem ⋮ Approximation algorithm for minimum connected 3-path vertex cover ⋮ Approximation algorithms for minimum weight connected 3-path vertex cover ⋮ A multi-start iterated greedy algorithm for the minimum weight vertex cover \(P_3\) problem ⋮ Kernels for packing and covering problems ⋮ Unnamed Item ⋮ Faster parameterized algorithm for cluster vertex deletion ⋮ Algorithm for online 3-path vertex cover ⋮ A Parameterized Algorithm for Bounded-Degree Vertex Deletion ⋮ Partitioning a graph into small pieces with applications to path transversal ⋮ Parameterized algorithm for 3-path vertex cover ⋮ Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing} ⋮ Approximation algorithms for hitting subgraphs

Cites Work

• A fixed-parameter algorithm for the vertex cover \(P_3\) problem
• 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
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
• Minimum \(k\)-path vertex cover
• The complexity of dissociation set problems in graphs
• The vertex cover \(P_3\) problem in cubic graphs
• A 2-approximation algorithm for the vertex coverP₄problem in cubic graphs
• A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion
• Mixing Color Coding-Related Techniques
• Node-Deletion Problems on Bipartite Graphs
• The complexity of restricted spanning tree problems

This page was built for publication: A faster FPT algorithm for 3-path vertex cover