On the Complexity of Computing Treelength

DOI10.1007/978-3-540-74456-6_26MaRDI QIDQ3525576zbMATH OpenOpenAlexFDO

Authors Daniel Lokshtanov

Publication date 17 September 2008

Published in Mathematical Foundations of Computer Science 2007 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-74456-6_26

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On the complexity of computing treelength
• On the complexity of computing treebreadth
• On the complexity of computing treebreadth
• Tree-decompositions with bags of small diameter
• To approximate treewidth, use treelength!

Cited in

(16)

• Tree-length equals branch-length
• On the complexity of computing treebreadth
• Tree-decompositions with bags of small diameter
• Treewidth computation and extremal combinatorics
• A revisit of the scheme for computing treewidth and minimum fill-in
• On the complexity of computing treebreadth
• Computing Tree-Depth Faster Than 2 n
• Differential geometric treewidth estimation in adiabatic quantum computation
• Complexity of computation of a spanning tree enumeration algorithm
• scientific article; zbMATH DE number 895329 (Why is no real title available?)
• scientific article; zbMATH DE number 1400211 (Why is no real title available?)
• On the recursion depth of special tree traversal algorithms
• Tree decompositions and social graphs
• Treelength of series-parallel graphs
• Complexity analysis of tree share structure
• On the complexity of computing treelength

This page was built for publication: On the Complexity of Computing Treelength

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