Spanners for bounded tree-length graphs
From MaRDI portal
Publication:2383601
DOI10.1016/j.tcs.2007.03.058zbMath1123.68087OpenAlexW1995114081MaRDI QIDQ2383601
Feodor F. Dragan, Yon Dourisboure, Chenyu Yan, Cyril Gavoille
Publication date: 19 September 2007
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2007.03.058
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12)
Related Items (13)
Additive tree \(O(\rho \log n)\)-spanners from tree breadth \(\rho \) ⋮ Computing the union join and subset graph of acyclic hypergraphs in subquadratic time ⋮ Tree-decompositions with bags of small diameter ⋮ 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 ⋮ Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs ⋮ On the complexity of computing treebreadth ⋮ Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences ⋮ On the complexity of computing treelength ⋮ Parameterized approximation algorithms for some location problems in graphs ⋮ An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs ⋮ On the Complexity of Computing Treebreadth ⋮ Tree-length equals branch-length
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Tree 3-spanners on interval, permutation and regular bipartite graphs
- Extremal graphs with no \(C^{4,}\)s, \(C^{6,}\)s, or \(C^{10,}\)s
- On sparse spanners of weighted graphs
- The Moore bound for irregular graphs
- A note on distance approximating trees in graphs
- Algorithms for maximum weight induced paths
- Tree spanners on chordal graphs: complexity and algorithms
- Tree-decompositions with bags of small diameter
- Additive sparse spanners for graphs with bounded length of largest induced cycle
- Design networks with bounded pairwise distance
- Graph minors. II. Algorithmic aspects of tree-width
- Graph spanners
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- Additive Tree Spanners
- Distributed Computing: A Locality-Sensitive Approach
- A trade-off between space and efficiency for routing tables
- An Optimal Synchronizer for the Hypercube
- Tree Spanners
- All-Pairs Almost Shortest Paths
- (1 + εΒ) -spanner constructions for general graphs
- Approximate distance oracles
- Structural Information and Communication Complexity
- Algorithm Theory - SWAT 2004
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Tree spanners in planar graphs
This page was built for publication: Spanners for bounded tree-length graphs
