Steiner Shallow-Light Trees Are Exponentially Lighter than Spanning Ones
From MaRDI portal
Publication:5502177
DOI10.1137/13094791XzbMath1319.05038OpenAlexW1764866826MaRDI QIDQ5502177
Publication date: 18 August 2015
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/13094791x
Trees (05C05) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Matrix multiplication via arithmetic progressions
- Sparse geometric graphs with small dilation
- Low-light trees, and tight lower bounds for Euclidean spanners
- Approximating buy-at-bulk and shallow-light \(k\)-Steiner trees
- The Steiner problem with edge lengths 1 and 2
- On sparse spanners of weighted graphs
- A new upper bound on the complexity of the all pairs shortest path problem
- Approximating the weight of shallow Steiner trees
- On approximating planar metrics by tree metrics.
- Approximating the Single-Sink Link-Installation Problem in Network Design
- Sublinear time algorithms for metric space problems
- Lower-Stretch Spanning Trees
- Distributed Multi-Destination Routing: The Constraints of Local Information
- Graph spanners
- Steiner Minimal Trees on Chinese Checkerboards
- Bicriteria Network Design Problems
- Improved Approximations for the Steiner Tree Problem
- A Graph-Theoretic Game and Its Application to the k-Server Problem
- Distributed Computing: A Locality-Sensitive Approach
- Light graphs with small routing cost
- Routing to Multiple Destinations in Computer Networks
- Approximation Algorithms for Directed Steiner Problems
- Using petal-decompositions to build a low stretch spanning tree
- Multiplying matrices faster than coppersmith-winograd
- Logarithmic Lower Bounds in the Cell-Probe Model
- Sparse Distance Preservers and Additive Spanners
- Steiner Minimal Trees
- Narrow-Shallow-Low-Light Trees with and without Steiner Points
- A tight bound on approximating arbitrary metrics by tree metrics