Polynomial bounds for the grid-minor theorem
DOI10.1145/2820609zbMATH Open1410.05186OpenAlexW2563767922MaRDI QIDQ3177816FDOQ3177816
Authors: Chandra Chekuri, Julia Chuzhoy 
Publication date: 2 August 2018
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2820609
Recommendations
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Structural characterization of families of graphs (05C75) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph minors (05C83) Parallel algorithms in computer science (68W10)
Cited In (35)
- Treewidth of graphs with balanced separations
- The grid theorem for vertex-minors
- Approximating Pathwidth for Graphs of Small Treewidth
- On tseitin formulas, read-once branching programs and treewidth
- Adapting the Directed Grid Theorem into an FPT Algorithm
- The Parameterized Complexity of Motion Planning for Snake-Like Robots
- Grid induced minor theorem for graphs of small degree
- Polynomial treedepth bounds in linear colorings
- Adapting the directed grid theorem into an \textsf{FPT} algorithm
- Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
- Bidimensionality and Kernels
- Constant Congestion Brambles
- Minor-Closed Graph Classes with Bounded Layered Pathwidth
- Finding Detours is Fixed-Parameter Tractable
- Polynomial treewidth forces a large grid-like-minor
- A Tight Erdös--Pósa Function for Wheel Minors
- Towards tight(er) bounds for the excluded grid theorem
- Deciding whether a grid is a topological subgraph of a planar graph is NP-complete
- Edge-treewidth: algorithmic and combinatorial properties
- Fractal dimension and lower bounds for geometric problems
- Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor
- Polynomials vanishing on grids: the Elekes-Rónyai problem revisited
- Packing Cycles Faster Than Erdos--Posa
- Unavoidable minors for graphs with large \(\ell_p\)-dimension
- Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion
- New limits of treewidth-based tractability in optimization
- On the parameterized complexity of freezing dynamics
- Title not available (Why is that?)
- Graph theory -- a survey on the occasion of the Abel Prize for László Lovász
- Extension complexity of the correlation polytope
- Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs
- Title not available (Why is that?)
- Contraction-Bidimensionality of Geometric Intersection Graphs
- On the impact of treewidth in the computational complexity of freezing dynamics
- Bounded-diameter tree-decompositions
This page was built for publication: Polynomial bounds for the grid-minor theorem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3177816)
