Recognition: unknown
Lower-Stretch Spanning Trees
classification
💻 cs.DS
cs.DM
keywords
spanningtreeaverageconstructcontainseverygraphlower-stretch
read the original abstract
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).
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.