Fetching the paper…
Reading the bibliography…
We present a new algorithm for generating a uniformly random spanning tree in an undirected graph.
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.
Random walks and electric networks
P. Doyle and J. Snell · 1984
Earlier work this paper cites.
λ 1 \lambda_{1} , isoperimetric inequalities for graphs and superconcentrators
N. Alon and V. Milman · 1985
Earlier work this paper cites.
Eigenvalues and expanders
N. Alon · 1986
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.
Covering problems for Brownian motion on spheres
P. Matthews · 1988
Earlier work this paper cites.
Generating random spanning trees
A. Broder · 1989
Earlier work this paper cites.
The electrical resistance of a graph captures its commute and cover times
A. K. Chandra, P. Raghavan, W. L. Ruzzo, and R. Smolensky · 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
Earlier work this paper cites.
Generating random combinatorial objects
V. G. Kulkarni · 1990
Earlier work this paper cites.
Random walks on graphs: A survey
L. Lovász · 1993
Earlier work this paper cites.
Two algorithms for unranking arborescences
C. J. Colbourn, W. J. Myrvold, and E. Neufeld · 1996
Cited alongside, same era.
Generating random spanning trees more quickly than the cover time
D. B. Wilson · 1996
Cited alongside, same era.
Modern Graph Theory
B. Bollobas · 1998
Cited alongside, same era.
Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
T. Leighton and S. Rao · 1999
Cited alongside, same era.
The cover time, the blanket time, and the Matthews bound
J. N. Kahn, J. H. Kim, L. Lovász, and V. H. Vu · 2000
Cited alongside, same era.
Solving sparse, symmetric, diagonally-dominant linear systems in time O ( m 1.31 ) {O}(m^{1.31})
D. A. Spielman and S.-H. Teng · 2003
Personal communication
J. Propp, 2010 · 2010
Later among the works it cites.
Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs
P. Christiano, J. Kelner, A. Mądry, D. Spielman, and S.-H. Teng · 2011
Later among the works it cites.
A nearly m log n m\log n -time solver for SDD linear systems
I. Koutis, G. L. Miller, and R. Peng · 2011
Later among the works it cites.
From Graphs to Matrices, and Back: New Techniques for Graph Algorithms
A. Mądry · 2011
Later among the works it cites.
A randomized rounding approach to the traveling salesman problem
S. Oveis Gharan, A. Saberi, and M. Singh · 2011
Later among the works it cites.
Cover times, blanket times, and majorizing measures
J. Ding, J. R. Lee, and Y. Peres · 2012
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
D. A. Spielman and S.-H. Teng · 2004
Cited alongside, same era.
Graph sparsification by effective resistances
D. A. Spielman and N. Srivastava · 2008
Cited alongside, same era.
Twice-Ramanujan sparsifiers
J. D. Batson, D. A. Spielman, and N. Srivastava · 2009
Cited alongside, same era.
Expanders via random spanning trees
N. Goyal, L. Rademacher, and S. Vempala · 2009
Cited alongside, same era.
Faster generation of random spanning trees
J. A. Kelner and A. Mądry · 2009
Cited alongside, same era.
Introduction to Probability Models, Tenth Edition
S. M. Ross · 2009
Cited alongside, same era.
Multiplying matrices faster than Coppersmith-Winograd
V. Vassilevska Williams · 2012
Later among the works it cites.
A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
J. A. Kelner, L. Orecchia, A. Sidford, and Z. A. Zhu · 2013
Later among the works it cites.
Graph partitioning using single commodity flows
T. C. Kwok, L. C. Lau, Y. T. Lee, S. Oveis Gharan, and L. Trevisan · 2013
Later among the works it cites.
Probability on Trees and Networks
Y. Lyons, R. with Peres · 2013
Later among the works it cites.
Navigating central path with electrical flows: from flows to matchings, and back
A. Mądry · 2013
Later among the works it cites.
Nearly maximum flows in nearly linear time
J. Sherman · 2013
Later among the works it cites.
An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
J. A. Kelner, Y. T. Lee, L. Orecchia, and A. Sidford · 2014
Later among the works it cites.
A note on cut-approximators and approximating undirected max flows
R. Peng · 2014
Later among the works it cites.