On the complexity of computing treelength

DOI10.1016/J.DAM.2009.10.007zbMath1201.68058OpenAlexW1980831620MaRDI QIDQ972342

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

approximationNP-completenessinapproximabilityexact exponential algorithmchordal sandwich problemgraph tree-length

Mathematics Subject Classification ID

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