An FPT algorithm for the vertex cover \(P_4\) problem
From MaRDI portal
Publication:906446
DOI10.1016/j.dam.2015.06.032zbMath1329.05287OpenAlexW880397381MaRDI QIDQ906446
Publication date: 21 January 2016
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2015.06.032
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (5)
An \(O^\ast ( 2 . 61 9^k )\) algorithm for \textsc{4-path vertex cover} ⋮ Computing connected-\(k\)-subgraph cover with connectivity requirement ⋮ Faster parameterized algorithms for two vertex deletion problems ⋮ Unnamed Item ⋮ On a relation between \(k\)-path partition and \(k\)-path vertex cover
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the weighted \(k\)-path vertex cover problem
- A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
- Finding odd cycle transversals.
- Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
- Improved algorithms for feedback vertex set problems
- Fixed-parameter algorithms for cluster vertex deletion
- The node-deletion problem for hereditary properties is NP-complete
- Fixed-parameter tractability of graph modification problems for hereditary properties
- On the \(k\)-path vertex cover of some graph products
- Minimum \(k\)-path vertex cover
- Another disjoint compression algorithm for odd cycle transversal
- On the vertex \(k\)-path cover
- A 2-approximation algorithm for the vertex coverP4problem in cubic graphs
- A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems
This page was built for publication: An FPT algorithm for the vertex cover \(P_4\) problem