Steiner shallow-light trees are exponentially lighter than spanning ones
DOI10.1137/13094791XzbMATH Open1319.05038OpenAlexW1764866826MaRDI QIDQ5502177FDOQ5502177
Authors: Michael Elkin, Shay Solomon 
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
Recommendations
Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Network design and communication in computer systems (68M10)
Cites Work
- Introduction to algorithms
- Approximating the weight of shallow Steiner trees
- Improved Approximations for the Steiner Tree Problem
- Distributed Computing: A Locality-Sensitive Approach
- Title not available (Why is that?)
- Approximation Algorithms for Directed Steiner Problems
- Multiplying matrices faster than coppersmith-winograd
- Matrix multiplication via arithmetic progressions
- Steiner Minimal Trees
- On sparse spanners of weighted graphs
- Graph spanners
- Routing to Multiple Destinations in Computer Networks
- Title not available (Why is that?)
- A tight bound on approximating arbitrary metrics by tree metrics
- Sublinear time algorithms for metric space problems
- A Graph-Theoretic Game and Its Application to the k-Server Problem
- A new upper bound on the complexity of the all pairs shortest path problem
- The Steiner problem with edge lengths 1 and 2
- Light graphs with small routing cost
- Lower-Stretch Spanning Trees
- Title not available (Why is that?)
- Approximating the single-sink link-installation problem in network design
- On approximating planar metrics by tree metrics.
- Steiner points in tree metrics don't (really) help
- Logarithmic Lower Bounds in the Cell-Probe Model
- Sparse geometric graphs with small dilation
- Distributed Multi-Destination Routing: The Constraints of Local Information
- Low-light trees, and tight lower bounds for Euclidean spanners
- Approximating buy-at-bulk and shallow-light \(k\)-Steiner trees
- Steiner Minimal Trees on Chinese Checkerboards
- Using petal-decompositions to build a low stretch spanning tree
- Sparse Distance Preservers and Additive Spanners
- Narrow-Shallow-Low-Light Trees with and without Steiner Points
- Title not available (Why is that?)
Cited In (6)
This page was built for publication: Steiner shallow-light trees are exponentially lighter than spanning ones
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5502177)
