A polynomial excluded-minor approximation of treedepth

DOI10.4171/JEMS/1133zbMath1485.05171OpenAlexW3208789479MaRDI QIDQ2119392

Benjamin Rossman, Ken-ichi Kawarabayashi

Publication date: 29 March 2022

Published in: Journal of the European Mathematical Society (JEMS) (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4171/jems/1133

zbMATH Keywords

excluded minortreedepth

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph minors (05C83)

Related Items (1)

Approximating Pathwidth for Graphs of Small Treewidth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Forbidden graphs for tree-depth
• Sparsity. Graphs, structures, and algorithms
• Computing tree-depth faster than \(2^n\)
• Graph minors. XX: Wagner's conjecture
• On low tree-depth decompositions
• Uniqueness and minimal obstructions for tree-depth
• On computing graph minor obstruction sets
• Optimal node ranking of tree in linear time
• Ordered colourings
• Towards tight(er) bounds for the excluded grid theorem
• Polynomial treedepth bounds in linear colorings
• Width, depth, and space: tradeoffs between branching and dynamic programming
• Tree-depth, subgraph coloring and homomorphism bounds
• A $c^k n$ 5-Approximation Algorithm for Treewidth
• Homomorphism preservation theorems
• Definability by constant-depth polynomial-size circuits
• Monotone versus positive
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Color-coding
• Formulas versus Circuits for Small Distance Connectivity
• Improved Bounds for the Excluded-Minor Approximation of Treedepth
• A Faster Parameterized Algorithm for Treedepth
• Polynomial bounds for the grid-minor theorem

This page was built for publication: A polynomial excluded-minor approximation of treedepth