Re:The Unreasonable Effectiveness of Spectral Graph Theory: ...
by espeed on Monday November 16, 2015 @12:11PM
(#10575584)
"Using Petal-Decompositions to Build a Low Stretch Spanning Tree" (http://research.microsoft.com/pubs/163400/spanning-full1.pdf):
Stretch: O(log n log log n)
Time: O(m log n log log n)
Good luck coding it though, I'm still looking for an implementation of a low stretch spanning tree (needed in order for the solver to be really lineaR)