Nearly Tight Low Stretch Spanning Trees

Abstract

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 E <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">T~T</sub> [d <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">T</sub> (u, nu)/d <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">G</sub> (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.