Stretching Stretch
Jakub Pachocki
January 15, 2014

Over the past few years, low-stretch spanning trees have been finding increasing use in graph algorithms. In the first part of this talk, I will survey the existing methods for finding low-stretch spanning trees.

I will then present a generalized definition of stretch motivated by observations about the performance of existing algorithms employing LSSTs. This definition allows us to treat many classes of edges with coarser granularity, leading to a fast two-pass approach for finding LSSTs. I will describe this new algorithm in the last part of the talk.

This is joint work with Michael Cohen, Gary Miller, Richard Peng, and Shen Chen Xu.