Nearly Tight Low Stretch Spanning Trees

Nearly Tight Low Stretch Spanning Trees

-
Ofer Neiman, Courant Institute, NYU
Fine Hall 224

We prove that any graph $G$ on $n$ vertices has a distribution over its spanning trees such that for any edge $(u,v)$ the expected stretch $E_T[d_T(u,v)]$ is bounded by $\tilde{O}(\log n)$. Our result is obtained via a new approach of building ``highways'' between portals and a new strong diameter probabilistic decomposition theorem. Joint work with Ittai Abraham and Yair Bartal