Nearly Tight Low Stretch Spanning Trees
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.