Improved Bounds for the Excluded-Minor Approximation of Treedepth

DOI10.1137/19M128819XzbMath1465.05174arXiv1904.13077OpenAlexW2977768445MaRDI QIDQ4990393

Wojciech Nadara, Wojciech Czerwiński, Marcin Pilipczuk

Publication date: 28 May 2021

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1904.13077

zbMATH Keywords

approximationtreewidthexcluded-minortreedepth

Mathematics Subject Classification ID

Graph minors (05C83) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

A polynomial excluded-minor approximation of treedepth ⋮ Tree-Depth and the Formula Complexity of Subgraph Isomorphism ⋮ Approximating Pathwidth for Graphs of Small Treewidth

Cites Work

• Unnamed Item
• Unnamed Item
• Forbidden graphs for tree-depth
• Sparsity. Graphs, structures, and algorithms
• On low tree-depth decompositions
• Optimal node ranking of tree in linear time
• Tree-depth, subgraph coloring and homomorphism bounds
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Graph minors. II. Algorithmic aspects of tree-width
• A Faster Parameterized Algorithm for Treedepth
• Towards Tight(er) Bounds for the Excluded Grid Theorem

This page was built for publication: Improved Bounds for the Excluded-Minor Approximation of Treedepth