Shallow, Low, and Light Trees, and Tight Lower Bounds for Euclidean Spanners

Yefim Dinitz, Michael Elkin, Shay Solomon

We show that for every $n$-point metric space $M$ there exists a spanning tree $T$ with unweighted diameter $O(\log n)$ and weight $\omega (T)=O(\log n)\cdot \omega (MST(M))$. Moreover, the…