On the complexity of computing treelength
DOI10.1016/J.DAM.2009.10.007zbMATH Open1201.68058OpenAlexW1980831620MaRDI QIDQ972342FDOQ972342
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
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
approximationexact exponential algorithmNP-completenessinapproximabilitychordal sandwich problemgraph tree-length
Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Treewidth Computation and Extremal Combinatorics
- Graph Sandwich Problems
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Incidence matrices and interval graphs
- Spanners for bounded tree-length graphs
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Minimal triangulations of graphs: a survey
- Treewidth and minimum fill-in: Grouping the minimal separators
- Exact Algorithms for Treewidth and Minimum Fill-In
- Algorithm Theory - SWAT 2004
- On treewidth and minimum fill-in of asteroidal triple-free graphs
- A characterisation of rigid circuit graphs
- Improved approximation algorithms for minimum-weight vertex separators
- Tree-decompositions with bags of small diameter
- Compact Routing Schemes for Bounded Tree-Length Graphs and for k-Chordal Graphs
Cited In (25)
- Title not available (Why is that?)
- An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs
- Title not available (Why is that?)
- An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs
- On the Complexity of Computing Treelength
- Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences
- Complexity analysis of tree share structure
- Burning two worlds
- Approximately counting locally-optimal structures
- On the recursion depth of special tree traversal algorithms
- On the complexity of computing treebreadth
- On the complexity of computing treebreadth
- Finding optimal triangulations parameterized by edge clique cover
- Title not available (Why is that?)
- Complexity of computation of a spanning tree enumeration algorithm
- Metric Dimension of Bounded Tree-length Graphs
- To approximate treewidth, use treelength!
- \(k\)-chordal graphs: from cops and robber to compact routing via treewidth
- Metric dimension of bounded width graphs
- A short note on the complexity of computing strong pathbreadth
- Treelength of series-parallel graphs
- Approximately Counting Locally-Optimal Structures
- Computing Tree-Depth Faster Than 2 n
- Line-distortion, bandwidth and path-length of a graph
- Tree-decompositions with bags of small diameter
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)
