A faster FPT algorithm for 3-path vertex cover

DOI10.1016/J.IPL.2015.12.002zbMATH Open1347.68182OpenAlexW2199703934MaRDI QIDQ903365FDOQ903365

Authors: 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/

Recommendations

• scientific article; zbMATH DE number 7561676
• Parameterized algorithm for 3-path vertex cover
• Faster computation of the maximum dissociation set and minimum 3-path vertex cover in graphs
• Kernelization and Parameterized Algorithms for 3-Path Vertex Cover
• A fixed-parameter algorithm for the vertex cover \(P_3\) problem
• Fixed-parameter algorithms for Vertex Cover \(P_3\)
• Approximation algorithm for minimum connected 3-path vertex cover
• Approximation algorithms for minimum weight connected 3-path vertex cover
• An improved algorithm for the vertex cover \(P_3\) problem on graphs of bounded treewidth
• An efficient polynomial time approximation scheme for the vertex cover \(P_3\) problem on planar graphs

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

• A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
• Minimum \(k\)-path vertex cover
• The vertex cover \(P_3\) problem in cubic graphs
• A 2-approximation algorithm for the vertex cover \(P_{4}\) problem in cubic graphs
• Mixing Color Coding-Related Techniques
• 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
• Node-Deletion Problems on Bipartite Graphs
• The complexity of restricted spanning tree problems
• A measure and conquer approach for the parameterized bounded degree-one vertex deletion
• The complexity of dissociation set problems in graphs

Cited In (34)

• An efficient polynomial time approximation scheme for the vertex cover \(P_3\) problem on planar graphs
• Partitioning a graph into small pieces with applications to path transversal
• Maximum dissociation sets in subcubic trees
• An improved algorithm for the vertex cover \(P_3\) problem on graphs of bounded treewidth
• On the weighted \(k\)-path vertex cover problem
• A fixed-parameter algorithm for the vertex cover \(P_3\) problem
• On the vertex cover \(P_3\) problem parameterized by treewidth
• Approximation algorithms for hitting subgraphs
• Computing connected-\(k\)-subgraph cover with connectivity requirement
• Approximation algorithm for minimum connected 3-path vertex cover
• Approximation algorithms for minimum weight connected 3-path vertex cover
• Kernelization of the 3-path vertex cover problem
• A multi-start iterated greedy algorithm for the minimum weight vertex cover \(P_3\) problem
• Approximation algorithm for minimum weight connected-\(k\)-subgraph cover
• Polynomial time recognition of vertices contained in all (or no) maximum dissociation sets of a tree
• The weighted \(k\)-path vertex cover problem on series-parallel graphs
• The geodesic-transversal problem
• Kernelization and Parameterized Algorithms for 3-Path Vertex Cover
• Faster parameterized algorithm for cluster vertex deletion
• Title not available (Why is that?)
• Approximation algorithm and FPT algorithm for connected-\(k\)-subgraph cover on minor-free graphs
• An FPT algorithm for the vertex cover \(P_4\) problem
• On the maximum number of maximum dissociation sets in trees with given dissociation number
• Faster parameterized algorithms for two vertex deletion problems
• Generating Faster Algorithms for d-Path Vertex Cover
• PTAS for minimum \(k\)-path vertex cover in ball graph
• Algorithm for online 3-path vertex cover
• Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
• Kernels for packing and covering problems
• A \(5k\)-vertex kernel for 3-path vertex cover
• An \(O^\ast ( 2 . 61 9^k )\) algorithm for \textsc{4-path vertex cover}
• Parameterized algorithm for 3-path vertex cover
• A parameterized algorithm for bounded-degree vertex deletion
• Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing}

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q903365)