Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
From MaRDI portal
Publication:1022348
DOI10.1007/S00453-007-9138-YzbMath1184.05121OpenAlexW1551708885MaRDI QIDQ1022348
Mohammad Taghi Hajiaghayi, Erik D. Demaine, Ken-ichi Kawarabayashi
Publication date: 22 June 2009
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-007-9138-y
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (13)
Neighborhood contraction in graphs ⋮ Graph Minors and Parameterized Algorithm Design ⋮ Grid minors in damaged grids ⋮ Connected search for a lazy robber ⋮ Low Polynomial Exclusion of Planar Graph Patterns ⋮ Contracting planar graphs to contractions of triangulations ⋮ Towards tight(er) bounds for the excluded grid theorem ⋮ Polynomial treewidth forces a large grid-like-minor ⋮ Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor ⋮ Complexity of the Steiner Network Problem with Respect to the Number of Terminals ⋮ Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness ⋮ Unnamed Item ⋮ Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness
Cites Work
- Graph minors. XX: Wagner's conjecture
- Quickly deciding minor-closed parameters in general graphs
- Linear connectivity forces large complete bipartite minors
- Graph minors. V. Excluding a planar graph
- Graph minors. X: Obstructions to tree-decomposition
- Highly connected sets and the excluded grid theorem
- Graph minors. XI: Circuits on a surface
- Call routing and the ratcatcher
- Quickly excluding a planar graph
- Diameter and treewidth in minor-closed graph families
- Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors
- Graph minors. IX: Disjoint crossed paths
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- \(K_{a,k}\) minors in graphs of bounded tree-width
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- Graph minors. XII: Distance on a surface
- Kernels in planar digraphs
- Excluding Minors in Nonplanar Graphs of Girth at Least Five
- Approximation Algorithms for Independent Sets in Map Graphs
- Vertex Cover: Further Observations and Further Improvements
- On Graph Powers for Leaf-Labeled Trees
- Map graphs
- Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
- Treewidth of planar graphs: connections with duality
- The Bidimensional Theory of Bounded-Genus Graphs
- Undirected ST-connectivity in log-space
- Graph minors. II. Algorithmic aspects of tree-width
- Nonconstructive tools for proving polynomial-time decidability
- Connectivity, graph minors, and subgraph multiplicity
- Parameterized complexity: exponential speed-up for planar graph problems
- Bidimensional Parameters and Local Treewidth
- Graph Drawing
- Ordering by Divisibility in Abstract Algebras
- The NP-completeness column: An ongoing guide
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
