Parameterized complexity: exponential speed-up for planar graph problems

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

Rolf Niedermeier, Jochen Alber, 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 complexityFixed-parameter tractabilityTree decompositionPlanar graph problemsGraph separators

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (24)

On the Parameterized Complexity of the Expected Coverage Problem ⋮ On the parameterized complexity of the expected coverage problem ⋮ Fixed-parameter approximation: conceptual framework and approximability results ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ Genus characterizes the complexity of certain graph problems: Some tight results ⋮ A graph-based algorithm for the multi-objective optimization of gene regulatory networks ⋮ Linear kernels for \(k\)-tuple and liar's domination in bounded genus graphs ⋮ On the vertex cover \(P_3\) problem parameterized by treewidth ⋮ A strengthened analysis of an algorithm for dominating set in planar graphs ⋮ Unnamed Item ⋮ Catalan structures and dynamic programming in \(H\)-minor-free graphs ⋮ Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions ⋮ Subexponential parameterized algorithms ⋮ Ranking and Drawing in Subexponential Time ⋮ Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms ⋮ Linearity of grid minors in treewidth with applications through bidimensionality ⋮ Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs ⋮ Parameterized algorithmics for linear arrangement problems ⋮ Bidimensionality and Kernels ⋮ Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction ⋮ Decomposition of Map Graphs with Applications. ⋮ Faster approximation schemes and parameterized algorithms on (odd-)\(H\)-minor-free graphs ⋮ A refined search tree technique for dominating set on planar graphs ⋮ Co-Roman domination in graphs

Uses Software

• LEDA

This page was built for publication: Parameterized complexity: exponential speed-up for planar graph problems