Low-light trees, and tight lower bounds for Euclidean spanners
From MaRDI portal
Publication:972609
DOI10.1007/s00454-009-9230-yzbMath1219.05184OpenAlexW1969939844MaRDI QIDQ972609
Michael Elkin, Shay Solomon, Yefim Dinitz
Publication date: 21 May 2010
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00454-009-9230-y
computational geometryapproximation algorithmsEuclidean spannershop-diameterlow distortion embeddings
Graph theory (including graph drawing) in computer science (68R10) Metric spaces, metrizability (54E35) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
Truly Optimal Euclidean Spanners, Minimum weight Euclidean \((1+\varepsilon)\)-spanners, New Doubling Spanners: Better and Simpler, Minimum weight Euclidean \((1+\varepsilon)\)-spanners, Light Spanners, Steiner Shallow-Light Trees Are Exponentially Lighter than Spanning Ones
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
- Constructing plane spanners of bounded degree and low weight
- An improved approximation ratio for the minimum linear arrangement problem
- Approximating \(k\)-hop minimum spanning trees in Euclidean metrics
- Well-separated pair decomposition in linear time?
- Approximating the weight of shallow Steiner trees
- Efficient construction of a bounded-degree spanner with low weight
- Approximating \(k\)-hop minimum-spanning trees
- Polylog-time and near-linear work approximation scheme for undirected shortest paths
- THE COMPLEXITY OF COMPUTING PARTIAL SUMS OFF-LINE
- Approximate Hierarchical Facility Location and Applications to the Shallow Steiner Tree and Range Assignment Problems
- Geometric Spanner Networks
- Lower-stretch spanning trees
- l22 spreading metrics for vertex ordering problems
- Distributed Multi-Destination Routing: The Constraints of Local Information
- Bicriteria Network Design Problems
- A Graph-Theoretic Game and Its Application to the k-Server Problem
- Distributed Computing: A Locality-Sensitive Approach
- Routing to Multiple Destinations in Computer Networks
- Network flow models for designing diameter‐constrained minimum‐spanning and Steiner trees
- Approximation Algorithms for Directed Steiner Problems
- Sparse communication networks and efficient routing in the plane (extended abstract)
- Compact routing on euclidian metrics
- A tight bound on approximating arbitrary metrics by tree metrics
- Small hop-diameter sparse spanners for doubling metrics
