Parameterized complexity: exponential speed-up for planar graph problems

DOI10.1016/J.JALGOR.2004.03.005MaRDI QIDQ4828563zbMATH OpenOpenAlexFDO

Authors Jochen Alber, Henning Fernau, Rolf Niedermeier

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

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

Recommendations

• scientific article; zbMATH DE number 1756013
• On parameterized exponential time complexity
• Mathematical Foundations of Computer Science 2004
• Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
• STACS 2004

Cited in

(32)

• Ranking and drawing in subexponential time
• STACS 2004
• Linearity of grid minors in treewidth with applications through bidimensionality
• On the vertex cover \(P_3\) problem parameterized by treewidth
• On the Parameterized Complexity of the Expected Coverage Problem
• A strengthened analysis of an algorithm for dominating set in planar graphs
• What's next? Future directions in parameterized complexity
• On the parameterized complexity of the expected coverage problem
• Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
• Why are CSPs based on partition schemes computationally hard?
• Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms
• Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
• On Parameterized Exponential Time Complexity
• A graph-based algorithm for the multi-objective optimization of gene regulatory networks
• Fixed-parameter approximation: conceptual framework and approximability results
• Catalan structures and dynamic programming in \(H\)-minor-free graphs
• scientific article; zbMATH DE number 1756013 (Why is no real title available?)
• Subexponential parameterized algorithms
• On parameterized exponential time complexity
• Parameterized algorithmics for linear arrangement problems
• Faster approximation schemes and parameterized algorithms on (odd-)\(H\)-minor-free graphs
• Co-Roman domination in graphs
• New plain-exponential time classes for graph homomorphism
• A refined search tree technique for dominating set on planar graphs
• Linear kernels for \(k\)-tuple and liar's domination in bounded genus graphs
• Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs
• scientific article; zbMATH DE number 1979505 (Why is no real title available?)
• Decomposition of Map Graphs with Applications.
• Bidimensionality and kernels
• Genus characterizes the complexity of certain graph problems: Some tight results
• scientific article; zbMATH DE number 2038758 (Why is no real title available?)
• Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up

Describes a project that uses

Uses Software

• LEDA

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4828563)