Name
Abstract | ||
|---|---|---|
We present a new algorithm for generating a uniformly random spanning tree in an undirected graph. Our algorithm samples such a tree in expected O(m4/3+o(1)) time. This improves over the best previously known bound of min(Õ(m[EQUATION]n), O(nω)) - that follows from the work of Kelner and Mądry [FOCS'09] and of Colbourn et al. [J. Algorithms'96] - whenever the input graph is sufficiently sparse. At a high level, our result stems from carefully exploiting the interplay of random spanning trees, random walks, and the notion of effective resistance, as well as from devising a way to algorithmically relate these concepts to the combinatorial structure of the graph. This involves, in particular, establishing a new connection between the effective resistance metric and the cut structure of the underlying graph. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.5555/2722129.2722263 | SODA |
DocType | Volume | ISBN |
Journal | abs/1501.00267 | 978-1-61197-433-1 |
Citations | PageRank | References |
7 | 0.44 | 30 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Aleksander Mądry | 1 | 961 | 45.38 |
| Damian Straszak | 2 | 52 | 7.08 |
| Jakub Tarnawski | 3 | 16 | 6.34 |