Parameterized complexity: exponential speed-up for planar graph problems

DOI10.1016/j.jalgor.2004.03.005zbMath1085.68102MaRDI QIDQ4828563

Jochen Alber, Rolf Niedermeier, Henning Fernau

Publication date: 23 November 2004

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jalgor.2004.03.005

zbMATH Keywords

Parameterized complexity; Fixed-parameter tractability; Tree decomposition; Planar graph problems; Graph separators

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Uses Software

• LEDA