On the complexity of computing treelength

DOI10.1016/J.DAM.2009.10.007MaRDI QIDQ972342zbMATH OpenOpenAlexFDO

Authors Daniel Lokshtanov

Publication date 25 May 2010

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2009.10.007

zbMATH Keywords

approximationexact exponential algorithmNP-completenessinapproximabilitychordal sandwich problemgraph tree-length

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) 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
• On the complexity of algorithms on recursive trees
• Tree enumeration and tree algorithm complexity computation
• Complexity of algorithm and operations on trees
• On the computational complexity of the theory of complete binary trees
• scientific article; zbMATH DE number 3854413
• A complexity calculus for recursive tree algorithms
• On treewidth approximations

Cites work

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A characterisation of rigid circuit graphs
• Algorithm Theory - SWAT 2004
• Compact Routing Schemes for Bounded Tree-Length Graphs and for k-Chordal Graphs
• Exact Algorithms for Treewidth and Minimum Fill-In
• Graph Sandwich Problems
• Improved approximation algorithms for minimum-weight vertex separators
• Incidence matrices and interval graphs
• Minimal triangulations of graphs: a survey
• On treewidth and minimum fill-in of asteroidal triple-free graphs
• Spanners for bounded tree-length graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Tree-decompositions with bags of small diameter
• Treewidth Computation and Extremal Combinatorics
• Treewidth and minimum fill-in: Grouping the minimal separators

Cited in

(25)

• Metric Dimension of Bounded Tree-length Graphs
• Complexity analysis of tree share structure
• \(k\)-chordal graphs: from cops and robber to compact routing via treewidth
• An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs
• To approximate treewidth, use treelength!
• Finding optimal triangulations parameterized by edge clique cover
• On the recursion depth of special tree traversal algorithms
• On the Complexity of Computing Treelength
• On the complexity of computing treebreadth
• scientific article; zbMATH DE number 895329 (Why is no real title available?)
• On the complexity of computing treebreadth
• Burning two worlds
• Tree-decompositions with bags of small diameter
• Approximately Counting Locally-Optimal Structures
• scientific article; zbMATH DE number 7764113 (Why is no real title available?)
• Treelength of series-parallel graphs
• An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs
• Line-distortion, bandwidth and path-length of a graph
• scientific article; zbMATH DE number 1400211 (Why is no real title available?)
• Metric dimension of bounded width graphs
• Complexity of computation of a spanning tree enumeration algorithm
• Approximately counting locally-optimal structures
• Computing Tree-Depth Faster Than 2 n
• A short note on the complexity of computing strong pathbreadth
• Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences

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 Q972342)