On the complexity of computing treelength
From MaRDI portal
Publication:972342
DOI10.1016/j.dam.2009.10.007zbMath1201.68058OpenAlexW1980831620MaRDI QIDQ972342
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
approximationNP-completenessinapproximabilityexact exponential algorithmchordal sandwich problemgraph tree-length
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (18)
Approximately counting locally-optimal structures ⋮ Approximately Counting Locally-Optimal Structures ⋮ Finding optimal triangulations parameterized by edge clique cover ⋮ Metric Dimension of Bounded Width Graphs ⋮ Treelength of series-parallel graphs ⋮ A short note on the complexity of computing strong pathbreadth ⋮ Unnamed Item ⋮ An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs ⋮ Burning Two Worlds ⋮ \(k\)-chordal graphs: from cops and robber to compact routing via treewidth ⋮ On the complexity of computing treebreadth ⋮ Algorithms parameterized by vertex cover and modular width, through potential maximal cliques ⋮ Line-distortion, bandwidth and path-length of a graph ⋮ Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences ⋮ To Approximate Treewidth, Use Treelength! ⋮ An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs ⋮ On the Complexity of Computing Treebreadth ⋮ Metric Dimension of Bounded Tree-length Graphs
Cites Work
- Minimal triangulations of graphs: a survey
- On treewidth and minimum fill-in of asteroidal triple-free graphs
- A characterisation of rigid circuit graphs
- Tree-decompositions with bags of small diameter
- Spanners for bounded tree-length graphs
- Incidence matrices and interval graphs
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Treewidth and Minimum Fill-in: Grouping the Minimal Separators
- Treewidth Computation and Extremal Combinatorics
- Improved approximation algorithms for minimum-weight vertex separators
- Exact Algorithms for Treewidth and Minimum Fill-In
- Graph Sandwich Problems
- Algorithm Theory - SWAT 2004
- Compact Routing Schemes for Bounded Tree-Length Graphs and for k-Chordal Graphs
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
This page was built for publication: On the complexity of computing treelength
