Lower-Stretch Spanning Trees
<|reference_start|>Lower-Stretch Spanning Trees: We prove that every weighted graph contains a spanning tree subgraph of average stretch O((log n log log n)^2). Moreover, we show how to construct such a tree in time O(m log^2 n).<|reference_end|>
@article{elkin2004lower-stretch,
    title={Lower-Stretch Spanning Trees},
    author={Michael Elkin, Yuval Emek, Daniel A. Spielman and Shang-Hua Teng},
    journal={arXiv preprint arXiv:cs/0411064},
    year={2004},
    archivePrefix={arXiv},
    eprint={cs/0411064},
    primaryClass={cs.DS cs.DM}
}