Title: Nearly Tight Low Stretch Spanning Trees.

Authors: Ittai Abraham, Yair Bartal, Ofer Neiman.

Abstract:

We prove that any graph G with n points has distribution over spanning trees such that for any
edge (u,v) the expected stretch E_T[d_T(u,v)/d_G(u,v)] is bounded by \tilde{O}(log n). 
Our result is obtained cia a new approach of building "highways" between portals and a new 
strong diameter probabilistic decomposition theorem.