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)
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ A Retrospective on (Meta) Kernelization ⋮ Contraction bidimensionality of geometric intersection graphs ⋮ Hitting Weighted Even Cycles in Planar Graphs ⋮ Towards the Graph Minor Theorems for Directed Graphs ⋮ Graph Minors and Parameterized Algorithm Design ⋮ Quickly deciding minor-closed parameters in general graphs ⋮ Unnamed Item ⋮ Layered separators in minor-closed graph classes with applications ⋮ Chasing a Fast Robber on Planar Graphs and Random Graphs ⋮ Structure of Graphs with Locally Restricted Crossings ⋮ The complexity of two graph orientation problems ⋮ Unnamed Item ⋮ Approximation algorithms via contraction decomposition ⋮ FPT approximation and subexponential algorithms for covering few or many edges ⋮ Catalan structures and dynamic programming in \(H\)-minor-free graphs ⋮ Output-polynomial enumeration on graphs of bounded (local) linear MIM-width ⋮ Minor-Closed Graph Classes with Bounded Layered Pathwidth ⋮ Subexponential parameterized algorithms ⋮ Confronting intractability via parameters ⋮ Spanners in sparse graphs ⋮ Orthogonal Tree Decompositions of Graphs ⋮ Linearity of grid minors in treewidth with applications through bidimensionality ⋮ Parameterized complexity of the spanning tree congestion problem ⋮ Contraction obstructions for treewidth ⋮ Optimality program in segment and string graphs ⋮ Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor ⋮ On \(H\)-topological intersection graphs ⋮ Bidimensionality and Kernels ⋮ Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction ⋮ Minimizing the Oriented Diameter of a Planar Graph
