Narrow-Shallow-Low-Light Trees with and without Steiner Points

DOI10.1137/090776147zbMath1227.68082OpenAlexW2090643701MaRDI QIDQ5894321

Michael Elkin, Shay Solomon

Publication date: 27 October 2011

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/8b305f847ab97ebc53ebd151609d9c062f128c9a

zbMATH Keywords

Steiner pointsfinite metric spacesspanning treesEuclidean spanners

Mathematics Subject Classification ID

Trees (05C05) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12)

Related Items (5)

Light Euclidean Spanners with Steiner Points ⋮ Sparse fault-tolerant spanners for doubling metrics with bounded hop-diameter or degree ⋮ Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics ⋮ Steiner Shallow-Light Trees Are Exponentially Lighter than Spanning Ones ⋮ On Hop-Constrained Steiner Trees in Tree-Like Metrics

This page was built for publication: Narrow-Shallow-Low-Light Trees with and without Steiner Points