Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
From MaRDI portal
Publication:1022348
DOI10.1007/S00453-007-9138-YzbMATH Open1184.05121OpenAlexW1551708885MaRDI QIDQ1022348FDOQ1022348
Authors: Erik D. Demaine, Mohammad T. Hajiaghayi, 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
Recommendations
- Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner’s Contraction
- Algorithmic Graph Minors and Bidimensionality
- Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality
- Mathematical Foundations of Computer Science 2004
- The Bidimensional Theory of Bounded-Genus Graphs
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph minors (05C83)
Cites Work
- Graph minors. X: Obstructions to tree-decomposition
- Title not available (Why is that?)
- Graph minors. XX: Wagner's conjecture
- Call routing and the ratcatcher
- Nonconstructive tools for proving polynomial-time decidability
- Title not available (Why is that?)
- Graph minors. V. Excluding a planar graph
- Highly connected sets and the excluded grid theorem
- Quickly excluding a planar graph
- Graph minors. II. Algorithmic aspects of tree-width
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
- Title not available (Why is that?)
- Bidimensionality: new connections between FPT algorithms and PTASs
- Diameter and treewidth in minor-closed graph families
- Graph minors. IX: Disjoint crossed paths
- Excluding minors in nonplanar graphs of girth at least five
- Vertex cover: Further observations and further improvements
- On graph powers for leaf-labeled trees
- Undirected ST-connectivity in log-space
- Ordering by Divisibility in Abstract Algebras
- Approximation algorithms for independent sets in map graphs
- Map graphs
- Equivalence of local treewidth and linear local treewidth and its algorithmic applications
- Linear connectivity forces large complete bipartite minors
- Graph minors. XII: Distance on a surface
- Title not available (Why is that?)
- Bidimensional Parameters and Local Treewidth
- Graph minors. XI: Circuits on a surface
- Kernels in planar digraphs
- Title not available (Why is that?)
- Parameterized complexity: exponential speed-up for planar graph problems
- Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality
- Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- Title not available (Why is that?)
- Title not available (Why is that?)
- The Bidimensional Theory of Bounded-Genus Graphs
- Graph Drawing
- The NP-completeness column: An ongoing guide
- Quickly deciding minor-closed parameters in general graphs
- \(K_{a,k}\) minors in graphs of bounded tree-width
- Title not available (Why is that?)
- Title not available (Why is that?)
- Connectivity, graph minors, and subgraph multiplicity
- Treewidth of planar graphs: connections with duality
- Title not available (Why is that?)
Cited In (18)
- Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner’s Contraction
- Title not available (Why is that?)
- Grid minors in damaged grids
- Neighborhood contraction in graphs
- Algorithmic Graph Minors and Bidimensionality
- Graph minors and parameterized algorithm design
- Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness
- Polynomial treewidth forces a large grid-like-minor
- Empirical evaluation of approximation algorithms for generalized graph coloring and uniform quasi-wideness
- Complexity of the Steiner Network Problem with Respect to the Number of Terminals
- Towards tight(er) bounds for the excluded grid theorem
- Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor
- Computation of Hadwiger number and related contraction problems. Tight lower bounds
- Low polynomial exclusion of planar graph patterns
- Contracting planar graphs to contractions of triangulations
- Contraction decomposition in \(h\)-minor-free graphs and algorithmic applications
- Connected search for a lazy robber
- Title not available (Why is that?)
This page was built for publication: Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1022348)
