An Improved FPT Algorithm and Quadratic Kernel for Pathwidth One Vertex Deletion
From MaRDI portal
Publication:3058695
DOI10.1007/978-3-642-17493-3_11zbMath1309.68090MaRDI 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
68Q25: Analysis of algorithms and problem complexity
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Two-layer planarization parameterized by feedback edge set, A polynomial kernel for block graph deletion, Hitting Forbidden Minors: Approximation and Kernelization, A Quartic Kernel for Pathwidth-One Vertex Deletion
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