Speaker: Shay Solomon (TAU)

Title: Euclidean Steiner Shallow-Light Trees

Abstract:
---------
A spanning tree that simultaneously approximates a shortest-path tree and a
minimum spanning tree is called a {shallow-light tree} (shortly, SLT).
Tight tradeoffs between the parameters of SLTs were established by Awerbuch
et al. in PODC'90 and by Khuller et al. in SODA'93.
I'll start by describing these SLTs constructions, which apply to general
graphs.
The main part of the talk will be devoted to constructions of SLTs for
point sets in the plane, and to the power of Steiner points in this context.

The talk will be self contained.