Faster generation of random spanning trees

Random walks, universal traversal sequences, and the complexity of maze problems

R. Aleliunas, R. M. Karp, R. J. Lipton, L. Lovász, and C. Rackoff · 1979

Earlier work this paper cites.

Graph theory: An introductory course

B. Bollobas · 1979

Earlier work this paper cites.

Random spanning tree

A. Guénoche · 1983

Earlier work this paper cites.

Estimating the coefficients of the reliability polynomial

C. J. Colbourn, B. M. Debroni, and W. J. Myrvold · 1988

Earlier work this paper cites.

Generating random spanning trees

A. Broder · 1989

Earlier work this paper cites.

Unranking and ranking spanning trees of a graph

C. J. Colbourn, R. P. J. Day, and L. D. Nel · 1989

Earlier work this paper cites.

A random walk construction of uniform spanning trees and uniform labelled trees

D. J. Aldous · 1990

Earlier work this paper cites.

Matrix multiplication via arithmetic progressions

D. Coppersmith and S. Winograd · 1990

Cited alongside, same era.

Generating random combinatorial objects

V. G. Kulkarni · 1990

Cited alongside, same era.

Random walks on graphs: A survey

L. Lovász · 1993

Cited alongside, same era.

Two algorithms for unranking arborescences

C. J. Colbourn, W. J. Myrvold, and E. Neufeld · 1996

Cited alongside, same era.

Shuffling biological sequences

D. Kandel, Y. Matias, R. Unger, and P. Winkler · 1996

Cited alongside, same era.

Generating random spanning trees more quickly than the cover time

Original

D. B. Wilson · 1996

Cited alongside, same era.

Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms

T. Leighton and S. Rao · 1999

Later among the works it cites.

Approximation algorithms for unique games

L. Trevisan · 2005

Later among the works it cites.

Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems

D. A. Spielman and S.-H. Teng · 2006

Later among the works it cites.

Graph sparsification by effective resistances

D. A. Spielman and N. Srivastava · 2008

Later among the works it cites.

Twice-ramanujan sparsifiers

J. Batson, D. A. Spielman, and N. Srivastava · 2009

Closest in time.

Expanders via random spanning trees

N. Goyal, L. Rademacher, and S. Vempala · 2009

Closest in time.