Improved bounds for the excluded-minor approximation of treedepth

DOI10.4230/LIPICS.ESA.2019.34MaRDI QIDQ5075772FDOQ5075772

Authors: Wojciech Czerwiński, Wojciech Nadara, Marcin Pilipczuk 

Publication date: 11 May 2022

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

zbMATH Keywords

excluded minortreedepth

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

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

Cited In (7)

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

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)