Polynomial bounds for the grid-minor theorem
From MaRDI portal
(Redirected from Publication:3177816)
Structural characterization of families of graphs (05C75) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph minors (05C83) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)
Recommendations
Cited in
(52)- Fractal dimension and lower bounds for geometric problems
- Unavoidable minors for graphs with large \(\ell_p\)-dimension
- On Tseitin formulas, read-once branching programs and treewidth
- The grid theorem for vertex-minors
- On the impact of treewidth in the computational complexity of freezing dynamics
- New limits of treewidth-based tractability in optimization
- A polynomial excluded-minor approximation of treedepth
- Adapting the directed grid theorem into an \textsf{FPT} algorithm
- Graph theory -- a survey on the occasion of the Abel Prize for László Lovász
- Towards tight(er) bounds for the excluded grid theorem
- Polynomial treedepth bounds in linear colorings
- Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor
- Extension complexity of the correlation polytope
- Treewidth of graphs with balanced separations
- Grid induced minor theorem for graphs of small degree
- Excluded grid theorem: improved and simplified
- Bidimensionality and kernels
- Grid minors in damaged grids
- Constant congestion routing of symmetric demands in planar directed graphs
- A polynomial excluded-minor approximation of treedepth
- Finding detours is fixed-parameter tractable
- Packing directed circuits quarter-integrally
- Adapting the directed grid theorem into an FPT algorithm
- Contraction-bidimensionality of geometric intersection graphs
- scientific article; zbMATH DE number 7236474 (Why is no real title available?)
- The parameterized complexity of motion planning for snake-like robots
- Minor-Closed Graph Classes with Bounded Layered Pathwidth
- Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
- Packing cycles faster than Erdős-Pósa
- Towards tight(er) bounds for the excluded grid theorem
- Polynomial planar directed grid theorem
- Polynomial bounds for the grid-minor theorem
- Improved bounds for the flat wall theorem
- A tight Erdős-Pósa function for wheel minors
- Large-treewidth graph decompositions and applications
- Deciding whether a grid is a topological subgraph of a planar graph is NP-complete
- Constant Congestion Brambles
- Edge-treewidth: algorithmic and combinatorial properties
- Approximating Pathwidth for Graphs of Small Treewidth
- On the parameterized complexity of freezing dynamics
- Bounded-diameter tree-decompositions
- Polynomial treewidth forces a large grid-like-minor
- Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion
- Algebraically grid-like graphs have large tree-width
- On the size of two minimal linkages
- Tight bound for the Erdős-Pósa property of tree minors
- Graph parameters, universal obstructions, and WQO
- Packing directed cycles quarter- and half-integrally
- Grid minors and products
- An exponential time parameterized algorithm for planar disjoint paths
- An FPT algorithm for the embeddability of graphs into two-dimensional simplicial complexes
- Uniform polynomial kernel for deletion to \(K_{2,p}\) minor-free graphs
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)
