An Improved FPT Algorithm and Quadratic Kernel for Pathwidth One Vertex Deletion

DOI10.1007/978-3-642-17493-3_11zbMath1309.68090OpenAlexW2628278606MaRDI QIDQ3058695

Marek Cygan, Jakub Onufry Wojtaszczyk, Marcin Pilipczuk, Michał Pilipczuk

Publication date: 7 December 2010

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-17493-3_11

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

A polynomial kernel for block graph deletion ⋮ Two-layer planarization parameterized by feedback edge set ⋮ A Quartic Kernel for Pathwidth-One Vertex Deletion ⋮ Hitting Forbidden Minors: Approximation and Kernelization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graphs and matching theorems
• Graph bandwidth of weighted caterpillars
• Graph minors. I. Excluding a forest
• The NP-completeness of the bandwidth minimization problem
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• A Quartic Kernel for Pathwidth-One Vertex Deletion
• The Proper Interval Colored Graph problem for caterpillar trees
• On Feedback Vertex Set New Measure and New Structures
• Graph minors. II. Algorithmic aspects of tree-width
• The Bandwidth of Caterpillars with Hairs of Length 1 and 2

This page was built for publication: An Improved FPT Algorithm and Quadratic Kernel for Pathwidth One Vertex Deletion