Bidimensional Parameters and Local Treewidth
From MaRDI portal
Publication:5317565
DOI10.1137/S0895480103433410zbMath1069.05070WikidataQ60488772 ScholiaQ60488772MaRDI QIDQ5317565
Erik D. Demaine, Dimitrios M. Thilikos, Fedor V. Fomin, Mohammad Taghi Hajiaghayi
Publication date: 16 September 2005
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Orthogonal Tree Decompositions of Graphs, Unnamed Item, Four Shorts Stories on Surprising Algorithmic Uses of Treewidth, A Retrospective on (Meta) Kernelization, Hitting Weighted Even Cycles in Planar Graphs, Minor-Closed Graph Classes with Bounded Layered Pathwidth, Structure of Graphs with Locally Restricted Crossings, Unnamed Item, Optimality program in segment and string graphs, On \(H\)-topological intersection graphs, The complexity of two graph orientation problems, Catalan structures and dynamic programming in \(H\)-minor-free graphs, Subexponential parameterized algorithms, Confronting intractability via parameters, Spanners in sparse graphs, Contraction bidimensionality of geometric intersection graphs, Quickly deciding minor-closed parameters in general graphs, Linearity of grid minors in treewidth with applications through bidimensionality, Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction, Output-polynomial enumeration on graphs of bounded (local) linear MIM-width, Parameterized complexity of the spanning tree congestion problem, Approximation algorithms via contraction decomposition, Contraction obstructions for treewidth, Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor, Layered separators in minor-closed graph classes with applications, Minimizing the Oriented Diameter of a Planar Graph, Graph Minors and Parameterized Algorithm Design, Chasing a Fast Robber on Planar Graphs and Random Graphs, Bidimensionality and Kernels, Towards the Graph Minor Theorems for Directed Graphs