A Faster Parameterized Algorithm for Treedepth
From MaRDI portal
Publication:5167804
DOI10.1007/978-3-662-43948-7_77zbMath1412.68089arXiv1401.7540OpenAlexW1532942816MaRDI QIDQ5167804
Somnath Sikdar, Fernando Sánchez Villaamil, Felix Reidl, Peter Rossmanith
Publication date: 1 July 2014
Published in: Automata, Languages, and Programming (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1401.7540
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
A polynomial excluded-minor approximation of treedepth ⋮ Parameterized Algorithms for Queue Layouts ⋮ Uniform Kernelization Complexity of Hitting Forbidden Minors ⋮ Eccentricity queries and beyond using hub labels ⋮ A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs ⋮ FPT algorithms to compute the elimination distance to bipartite graphs and more ⋮ On the lossy kernelization for connected treedepth deletion set ⋮ Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space ⋮ Polynomial kernels for hitting forbidden minors under structural parameterizations ⋮ Polynomial treedepth bounds in linear colorings ⋮ Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations. ⋮ The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth. ⋮ On the Parameterized Complexity of Clique Elimination Distance ⋮ Algorithms parameterized by vertex cover and modular width, through potential maximal cliques ⋮ Unnamed Item ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity ⋮ Faster Computation of Path-Width ⋮ Elimination Distance to Bounded Degree on Planar Graphs ⋮ Uniformly Automatic Classes of Finite Structures ⋮ Structural sparsity of complex networks: bounded expansion in random models and real-world graphs ⋮ Improved Bounds for the Excluded-Minor Approximation of Treedepth ⋮ How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs? ⋮ How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs ⋮ On vertex rankings of graphs and its relatives ⋮ Parameterized Algorithms for Queue Layouts
