Bidimensional Parameters and Local Treewidth

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)

zbMATH Keywords

dominating setgraph minors

Mathematics Subject Classification ID

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