Lower-Stretch Spanning Trees
Dan Spielman, MIT
Thursday, March 24th, 2005, 4:30 pm
Wean Hall 4623

A low-stretch spanning tree T of a graph G is a spanning tree subgraph in which most edges of G can be routed with small dilation. In particular, the stretch of an edge of G in T is the length of the path in T connecting the endpoints of that edge. The average stretch is the average over edges in G of their stretch.

In an analysis of an algorithm for the k-server problem, Alon, Karp, Peleg and West showed that there exist spanning trees of average stretch 2^(O(sqrt(n)). We were motivated to improve their construction because this average-stretch is the dominant term in the complexity of a new solver for diagonally-dominant systems of equations. We present a O(m log^2 n)-time algorithm that constructs trees of much lower average stretch: O(log^2 n log log n).

Joint work with Michael Elkin, Yuval Emek and Shang-Hua Teng.