To Approximate Treewidth, Use Treelength!

DOI10.1137/15M1034039zbMath1341.05238OpenAlexW2478689417MaRDI QIDQ5741086

David Coudert, Guillaume Ducoffe, Nicolas Nisse

Publication date: 22 July 2016

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/15m1034039

zbMATH Keywords

treewidthgenuscycle basistreelength

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (9)

Obstructions to a small hyperbolicity in Helly graphs ⋮ Data center interconnection networks are not hyperbolic ⋮ On the hyperbolicity of bipartite graphs and intersection graphs ⋮ Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem ⋮ Treelength of series-parallel graphs ⋮ A short note on the complexity of computing strong pathbreadth ⋮ On the complexity of computing treebreadth ⋮ On distance-preserving elimination orderings in graphs: complexity and algorithms ⋮ On the Complexity of Computing Treebreadth

Cites Work

• Unnamed Item
• Unnamed Item
• The decomposition of graphs into \(k\)-connected components
• Connected tree-width
• Finding the longest isometric cycle in a graph
• On the complexity of computing treelength
• Connected cutsets of a graph and triangle bases of the cycle space
• A partial k-arboretum of graphs with bounded treewidth
• On finding a cycle basis with a shortest maximal cycle
• Characterizations and algorithmic applications of chordal graph embeddings
• Vertex-to-vertex pursuit in a graph
• Contraction obstructions for treewidth
• Tree-decompositions with bags of small diameter
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• On the Tree-Width of Planar Graphs
• Recognition of $C_4$-Free and 1/2-Hyperbolic Graphs
• Metric Dimension of Bounded Width Graphs
• Weakly Modular Graphs and Nonpositive Curvature
• The Bidimensional Theory of Bounded-Genus Graphs
• Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
• Packing and Covering δ-Hyperbolic Spaces by Balls
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
• Tree decompositions and social graphs

This page was built for publication: To Approximate Treewidth, Use Treelength!