Fetching the paper…
Reading the bibliography…
We present an algorithm that, with high probability, generates a random spanning tree from an edge-weighted undirected graph in $\tilde{O}(n^{4/3}m^{1/2}+n^{2})$ time (The $\tilde{O}(\cdot)$ notation hides $\operatorname{polylog}(n)$ factors).
Random spanning tree
Alain Guenoche · 1983
Earlier work this paper cites.
Generating random spanning trees
Andrei Broder · 1989
Earlier work this paper cites.
Unranking and ranking spanning trees of a graph
Charles J Colbourn, Robert PJ Day, and Louis D Nel · 1989
Earlier work this paper cites.
The random walk construction of uniform spanning trees and uniform labelled trees
David Aldous · 1990
Earlier work this paper cites.
Generating random combinatorial objects
Vidyadhar G. Kulkarni · 1990
Earlier work this paper cites.
Two algorithms for unranking arborescences
Charles J Colbourn, Wendy J Myrvold, and Eugene Neufeld · 1996
Earlier work this paper cites.
Generating random spanning trees more quickly than the cover time
David Bruce Wilson · 1996
Earlier work this paper cites.
Expanders via random spanning trees
Navin Goyal, Luis Rademacher, and Santosh Vempala · 2009
Earlier work this paper cites.
Faster generation of random spanning trees
Jonathan Kelner and Aleksander Madry · 2009
Earlier work this paper cites.
An o(log n/ log log n)-approximation algorithm for the asymmetric traveling salesman problem
Arash Asadpour, Michel X. Goemans, Aleksander Mądry, Shayan Oveis Gharan, and Amin Saberi · 2010
Cited alongside, same era.
A randomized rounding approach to the traveling salesman problem
Shayan Oveis Gharan, Amin Saberi, and Mohit Singh · 2011
Cited alongside, same era.
A nearly-m log n time solver for SDD linear systems
Ioannis Koutis, Gary L. Miller, and Richard Peng · 2011
Cited alongside, same era.
Graph sparsification by effective resistances
Daniel A. Spielman and Nikhil Srivastava · 2011
Cited alongside, same era.
Multiplying matrices faster than coppersmith-winograd
Virginia Vassilevska Williams · 2012
Cited alongside, same era.
A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
Approaching optimality for solving sdd linear systems
I. Koutis, G. Miller, and R. Peng · 2014
Later among the works it cites.
Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems
Daniel A. Spielman and Shang-Hua Teng · 2014
Later among the works it cites.
Faster spectral sparsification and numerical algorithms for sdd matrices
Ioannis Koutis, Alex Levin, and Richard Peng · 2015
Later among the works it cites.
Fast generation of random spanning trees and the effective resistance metric
Aleksander Madry, Damian Straszak, and Jakub Tarnawski · 2015
Later among the works it cites.
Generating random spanning trees via fast matrix multiplication
Nicholas J. A. Harvey and Keyulu Xu · 2016
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, and Zeyuan Allen Zhu · 2013
Cited alongside, same era.
Efficient accelerated coordinate descent methods and faster algorithms for solving linear systems
Yin Tat Lee and Aaron Sidford · 2013
Cited alongside, same era.
Solving SDD linear systems in nearly m log 1 / 2 n m\log^{1/2}n time
Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Anup Rao, and Shen Chen Xu · 2014
Cited alongside, same era.
U ¨ \ddot{U} ber die aufl o ¨ \ddot{o} sung der gliechungen, auf welche man bei der untersuchung der linearen vertheilung galvanischer str o ¨ \ddot{o} me gef u ¨ \ddot{u} hrt wird
Gustav Kirchhoff
Cited in the paper.
Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Daniel A Spielman · 2016
Closest in time.
Approximate gaussian elimination for laplacians - fast, sparse, and simple
Rasmus Kyng and Sushant Sachdeva · 2016
Closest in time.
A framework for analyzing resparsification algorithms
Rasmus Kyng, Jakub Pachocki, Richard Peng, and Sushant Sachdeva · 2017
Closest in time.