Computing tree-depth faster than \(2^n\)

DOI10.1007/s00453-014-9914-4zbMath1337.68129arXiv1306.3857OpenAlexW2189938931WikidataQ60488387 ScholiaQ60488387MaRDI QIDQ493242

Archontia C. Giannopoulou, Michał Pilipczuk, Fedor V. Fomin

Publication date: 3 September 2015

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

exact algorithmstree-depth\(2^n\) barrier

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

A polynomial excluded-minor approximation of treedepth, Enumeration of minimal tropical connected sets, Unnamed Item, Algorithms parameterized by vertex cover and modular width, through potential maximal cliques

Cites Work

• Vertex ranking of asteroidal triple-free graphs
• Sparsity. Graphs, structures, and algorithms
• A note on exact algorithms for vertex ordering problems on graphs
• Graph minors. XX: Wagner's conjecture
• Optimal node ranking of tree in linear time
• Graph minors. XIII: The disjoint paths problem
• Ordered colourings
• On the vertex ranking problem for trapezoid, circular-arc and other graphs
• Treewidth computation and extremal combinatorics
• Grad and classes with bounded expansion. I: Decompositions
• Grad and classes with bounded expansion. II: Algorithmic aspects
• Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities
• Tree-depth, subgraph coloring and homomorphism bounds
• On Cutwidth Parameterized by Vertex Cover
• A Dynamic Programming Approach to Sequencing Problems
• Exact Algorithms for Treewidth and Minimum Fill-In
• Computing Pathwidth Faster Than 2 n
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Rankings of Graphs
• Computing Directed Pathwidth in O(1.89 n ) Time