Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
From MaRDI portal
(Redirected from Publication:1022348)
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
Cites work
- scientific article; zbMATH DE number 1222597 (Why is no real title available?)
- scientific article; zbMATH DE number 475621 (Why is no real title available?)
- scientific article; zbMATH DE number 1057879 (Why is no real title available?)
- scientific article; zbMATH DE number 1947048 (Why is no real title available?)
- scientific article; zbMATH DE number 1953101 (Why is no real title available?)
- scientific article; zbMATH DE number 2044919 (Why is no real title available?)
- scientific article; zbMATH DE number 2038758 (Why is no real title available?)
- scientific article; zbMATH DE number 1929955 (Why is no real title available?)
- scientific article; zbMATH DE number 1432797 (Why is no real title available?)
- scientific article; zbMATH DE number 6469239 (Why is no real title available?)
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- Approximation algorithms for independent sets in map graphs
- Bidimensional Parameters and Local Treewidth
- Bidimensionality: new connections between FPT algorithms and PTASs
- Call routing and the ratcatcher
- Connectivity, graph minors, and subgraph multiplicity
- Diameter and treewidth in minor-closed graph families
- Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
- Equivalence of local treewidth and linear local treewidth and its algorithmic applications
- Excluding minors in nonplanar graphs of girth at least five
- Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- Graph Drawing
- Graph minors. II. Algorithmic aspects of tree-width
- Graph minors. IX: Disjoint crossed paths
- Graph minors. V. Excluding a planar graph
- Graph minors. X: Obstructions to tree-decomposition
- Graph minors. XI: Circuits on a surface
- Graph minors. XII: Distance on a surface
- Graph minors. XX: Wagner's conjecture
- Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality
- Highly connected sets and the excluded grid theorem
- Kernels in planar digraphs
- Linear connectivity forces large complete bipartite minors
- Map graphs
- Nonconstructive tools for proving polynomial-time decidability
- On graph powers for leaf-labeled trees
- Ordering by Divisibility in Abstract Algebras
- Parameterized complexity: exponential speed-up for planar graph problems
- Quickly deciding minor-closed parameters in general graphs
- Quickly excluding a planar graph
- The Bidimensional Theory of Bounded-Genus Graphs
- The NP-completeness column: An ongoing guide
- Treewidth of planar graphs: connections with duality
- Undirected ST-connectivity in log-space
- Vertex cover: Further observations and further improvements
- \(K_{a,k}\) minors in graphs of bounded tree-width
Cited in
(18)- Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner’s Contraction
- Grid minors in damaged grids
- scientific article; zbMATH DE number 5874803 (Why is no real title available?)
- Neighborhood contraction in graphs
- Algorithmic Graph Minors and Bidimensionality
- Graph minors and parameterized algorithm design
- 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
- Empirical evaluation of approximation algorithms for generalized graph coloring and uniform quasi-wideness
- 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
- Low polynomial exclusion of planar graph patterns
- Computation of Hadwiger number and related contraction problems. Tight lower bounds
- Contracting planar graphs to contractions of triangulations
- Contraction decomposition in \(h\)-minor-free graphs and algorithmic applications
- Connected search for a lazy robber
- scientific article; zbMATH DE number 7053376 (Why is no real title available?)
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)
