Towards Tight(er) Bounds for the Excluded Grid Theorem

DOI10.1137/1.9781611975482.88zbMath1434.05146OpenAlexW2902524093MaRDI QIDQ5236272

Julia Chuzhoy, Zihan Tan

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611975482.88

zbMATH Keywords

treewidthfixed parameter tractabilitygraph decompositiongrid minor theoremErdős-Pósa theorems

Mathematics Subject Classification ID

Graph minors (05C83)

Related Items (14)

Tree-Depth and the Formula Complexity of Subgraph Isomorphism ⋮ Finding a maximum minimal separator: graph classes and fixed-parameter tractability ⋮ Adapting the Directed Grid Theorem into an FPT Algorithm ⋮ The Parameterized Complexity of Motion Planning for Snake-Like Robots ⋮ Minor-Closed Graph Classes with Bounded Layered Pathwidth ⋮ Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs ⋮ Unnamed Item ⋮ Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor ⋮ Unavoidable minors for graphs with large \(\ell_p\)-dimension ⋮ Finding Detours is Fixed-Parameter Tractable ⋮ Elimination Distance to Bounded Degree on Planar Graphs ⋮ Improved Bounds for the Excluded-Minor Approximation of Treedepth ⋮ Bounded-depth Frege complexity of Tseitin formulas for all graphs ⋮ On the maximum weight minimal separator

This page was built for publication: Towards Tight(er) Bounds for the Excluded Grid Theorem