Parameterized complexity: exponential speed-up for planar graph problems
DOI10.1016/J.JALGOR.2004.03.005zbMATH Open1085.68102OpenAlexW2108093643MaRDI QIDQ4828563FDOQ4828563
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
Recommendations
Parameterized complexityFixed-parameter tractabilityTree decompositionPlanar graph problemsGraph separators
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)
Cited In (32)
- Ranking and drawing in subexponential time
- STACS 2004
- On the vertex cover \(P_3\) problem parameterized by treewidth
- Linearity of grid minors in treewidth with applications through bidimensionality
- On the Parameterized Complexity of the Expected Coverage Problem
- What's next? Future directions in parameterized complexity
- A strengthened analysis of an algorithm for dominating set in planar graphs
- 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
- Fixed-parameter approximation: conceptual framework and approximability results
- A graph-based algorithm for the multi-objective optimization of gene regulatory networks
- Title not available (Why is that?)
- Catalan structures and dynamic programming in \(H\)-minor-free graphs
- 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
- A refined search tree technique for dominating set on planar graphs
- New plain-exponential time classes for graph homomorphism
- 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
- Title not available (Why is that?)
- Decomposition of Map Graphs with Applications.
- Bidimensionality and kernels
- Genus characterizes the complexity of certain graph problems: Some tight results
- Title not available (Why is that?)
- Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
Uses Software
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)
