Parameterized complexity: exponential speed-up for planar graph problems
From MaRDI portal
Publication:4828563
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
Parameterized complexityFixed-parameter tractabilityTree decompositionPlanar graph problemsGraph separators
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
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
