# Fast Generation of Random Spanning Trees and the Effective Resistance Metric

arXiv: https://arxiv.org/abs/1501.00267 · HTML: https://mlsanity.com/paper/1501.00267/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jan 2015.

## Built on by (most cited first, 4 of 4)

- [Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence](https://mlsanity.com/paper/2204.02570/) (2022)
- [Local Algorithms for Estimating Effective Resistance](https://mlsanity.com/paper/2106.03476/) (2021)
- [Sparsification of the regularized magnetic Laplacian with multi-type spanning forests](https://mlsanity.com/paper/2208.14797/) (2022)
- [Efficient Edge Rewiring Strategies for Enhancing PageRank Fairness](https://mlsanity.com/paper/2602.02512/) (2026)

## Abstract (arXiv)

We present a new algorithm for generating a uniformly random spanning tree in an undirected graph. Our algorithm samples such a tree in expected tildeO(m4/3) time. This improves over the best previously known bound of min(tildeO(m√n),O(nω)) -- that follows from the work of Kelner and Mkadry [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.