Tree-decompositions with bags of small diameter

DOI10.1016/j.disc.2005.12.060zbMath1118.05077OpenAlexW2126464568MaRDI QIDQ2370441

Cyril Gavoille, Yon Dourisboure

Publication date: 26 June 2007

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

Full work available at URL: https://doi.org/10.1016/j.disc.2005.12.060

zbMATH Keywords

chordalitytree-widthtree-decompositiontree-lengthsmall separator

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Additive tree \(O(\rho \log n)\)-spanners from tree breadth \(\rho \), How to use spanning trees to navigate in graphs, A survey of graph burning, How to Use Spanning Trees to Navigate in Graphs, Spanners for bounded tree-length graphs, Injective hulls of various graph classes, Treewidth computation and extremal combinatorics, Applying clique-decomposition for computing Gromov hyperbolicity, Helly-gap of a graph and vertex eccentricities, Metric Dimension of Bounded Width Graphs, Treelength of series-parallel graphs, Pathlength of outerplanar graphs, On Strong Tree-Breadth, Treewidth versus clique number. II: Tree-independence number, Additive spanners and distance and routing labeling schemes for hyperbolic graphs, A short note on the complexity of computing strong pathbreadth, Revisiting Decomposition by Clique Separators, An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs, Burning Two Worlds, Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs, Bounding the Order of a Graph Using Its Diameter and Metric Dimension: A Study Through Tree Decompositions and VC Dimension, \(k\)-chordal graphs: from cops and robber to compact routing via treewidth, On the complexity of computing treebreadth, 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!, On the complexity of computing treelength, Connected tree-width, Control of Some Graph Invariants in Dynamic Routing, Fast approximation of eccentricities and distances in hyperbolic graphs, An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs, Universal augmentation schemes for network navigability, On the Complexity of Computing Treebreadth, Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs, Tree-length equals branch-length, On the Tree-Width of Planar Graphs, Tree decompositions and social graphs, Metric Dimension of Bounded Tree-length Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Decomposition by clique separators
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• A linear algorithm for embedding planar graphs using PQ-trees
• A unified approach to domination problems on interval graphs
• An algorithm for finding clique cut-sets
• A partial k-arboretum of graphs with bounded treewidth
• Treewidth for graphs with small chordality
• Characterizations and algorithmic applications of chordal graph embeddings
• Query efficient implementation of graphs of bounded clique-width
• Diameter and treewidth in minor-closed graph families
• A note on distance approximating trees in graphs
• Tree spanners on chordal graphs: complexity and algorithms
• Spanners for bounded tree-length graphs
• Design networks with bounded pairwise distance
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• Total Domination and Irredundance in Weighted Interval Graphs
• Graph spanners
• Dominating Sets in Chordal Graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Distributed Computing: A Locality-Sensitive Approach
• A trade-off between space and efficiency for routing tables
• An Optimal Synchronizer for the Hypercube
• Tree Spanners
• Proximity-preserving labeling schemes
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Algorithms - ESA 2003
• Tree spanners in planar graphs