Steiner Shallow-Light Trees Are Exponentially Lighter than Spanning Ones

DOI10.1137/13094791XzbMath1319.05038OpenAlexW1764866826MaRDI QIDQ5502177

Shay Solomon, Michael Elkin

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

zbMATH Keywords

minimum spanning treeSteiner treeSteiner pointshortest-path treeshallow-light tree

Mathematics Subject Classification ID

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

Euclidean Steiner Spanners: Light and Sparse ⋮ Light Euclidean Spanners with Steiner Points

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