Improved bounds for the excluded-minor approximation of treedepth

DOI10.4230/LIPICS.ESA.2019.34MaRDI QIDQ5075772zbMATH OpenFDO

Authors Wojciech Czerwiński, Wojciech Nadara, Marcin Pilipczuk

Publication date 11 May 2022

Full work available at URL https://doi.org/10.4230/LIPICS.ESA.2019.34

zbMATH Keywords

excluded minortreedepth

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Improved bounds for the excluded-minor approximation of treedepth
• A polynomial excluded-minor approximation of treedepth
• A polynomial excluded-minor approximation of treedepth
• Tight bound on treedepth in terms of pathwidth and longest path
• A faster parameterized algorithm for treedepth

Cites work

• A faster parameterized algorithm for treedepth
• A polynomial excluded-minor approximation of treedepth
• Forbidden graphs for tree-depth
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• On low tree-depth decompositions
• Sparsity. Graphs, structures, and algorithms
• Towards tight(er) bounds for the excluded grid theorem
• Tree-depth, subgraph coloring and homomorphism bounds

Cited in

(8)

• Polynomial treedepth bounds in linear colorings
• Local tree-width, excluded minors, and approximation algorithms
• On the Parameterized Complexity of Clique Elimination Distance
• The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth.
• Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space
• Tight bound on treedepth in terms of pathwidth and longest path
• On the size of minimal separators for treedepth decomposition
• Lower bounds on dynamic programming for maximum weight independent set

This page was built for publication: Improved bounds for the excluded-minor approximation of treedepth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5075772)