Nearly Tight Low Stretch Spanning Trees

Ittai Abraham, Yair Bartal, Ofer Neiman

We prove that any graph $G$ with $n$ points has a distribution $\mathcal{T}$ over spanning trees such that for any edge $(u,v)$ the expected stretch $E_{T \sim \mathcal{T}}[d_T(u,v…