On approximating tree spanners that are breadth first search trees
From MaRDI portal
Publication:269500
DOI10.1016/j.jcss.2016.02.008zbMath1338.68222arXiv1506.02243OpenAlexW2287355843MaRDI QIDQ269500
Publication date: 18 April 2016
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1506.02243
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items
Cites Work
- Unnamed Item
- Reconstructing the shape of a tree from observed dissimilarity data
- An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs
- Trigraphs
- Lower bounds on the distortion of embedding finite metric spaces in graphs
- Low complexity variants of the arrow distributed directory
- Tree spanners of bounded degree graphs
- There are planar graphs almost as good as the complete graph
- Tree spanners on chordal graphs: complexity and algorithms
- Spanners of bounded degree graphs
- Low distortion spanners
- Geometric Spanner Networks
- Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
- Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs
- Complexity of network synchronization
- Planar spanners and approximate shortest path queries among obstacles in the plane
- An Optimal Synchronizer for the Hypercube
- Tree Spanners
- A tight bound on approximating arbitrary metrics by tree metrics
- Tree spanners in planar graphs
