Title: Nearly Tight Low Stretch Spanning Trees
Speaker: Ofer Neiman, NYU
Abstract:
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