An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion

DOI10.1007/s00453-011-9578-2zbMath1252.68150MaRDI QIDQ1759683

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

Publication date: 21 November 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-011-9578-2

zbMATH Keywords

fixed parameter tractability; pathwidth; kernelization; caterpillar graph

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)