Tree-decompositions with bags of small diameter

DOI10.1016/j.disc.2005.12.060zbMath1118.05077MaRDI 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

chordality; tree-width; tree-decomposition; tree-length; small separator

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

Related Items

Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs, On the complexity of computing treelength, Universal augmentation schemes for network navigability, Tree-length equals branch-length, Spanners for bounded tree-length graphs, Additive spanners and distance and routing labeling schemes for hyperbolic graphs, An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs, How to Use Spanning Trees to Navigate in Graphs, Control of Some Graph Invariants in Dynamic Routing

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
• 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
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Algorithms - ESA 2003
• Tree spanners in planar graphs