Nearly Tight Low Stretch Spanning Trees
Ittai Abraham, Yair Bartal, Ofer Neiman · 2008
We prove that any graph G with n points has a distribution T over spanning trees such that for any edge (u, v) the expected stretch ET~T[dT(u, nu)/dG(u, nu)] is bounded by Otilde(log n). Our result is obtained via a new approach of building "highways" between portals and a new strong diameter probabilistic decomposition theorem.