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

Fixed-parameter tractabilityGraph separatorsParameterized complexityPlanar graph problemsTree decomposition

Mathematics Subject Classification ID

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

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

(33)

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

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)