“Lower-Stretch Spanning Trees”, Michael Elkin, Yuval Emek, Daniel A. Spielman, Shang-Hua Teng2004-11-17 (algorithms; backlinks):
We prove that every weighted graph contains a spanning tree subgraph of average stretch 𝒪(log2 n log log n). Moreover, we show how to construct such a tree in time 𝒪(m log n + n log2 n). Backlinks:
We prove that every weighted graph contains a spanning tree subgraph of average stretch 𝒪(log2 n log log n).
Moreover, we show how to construct such a tree in time 𝒪(m log n + n log2 n).
Backlinks: