Fetching the paper…
Reading the bibliography…
We give an $m^{1+o(1)}\beta^{o(1)}$-time algorithm for generating a uniformly random spanning tree in an undirected, weighted graph with max-to-min weight ratio $\beta$.
Adjustment of an inverse matrix corresponding to a change in one element of a given matrix
Jack Sherman and Winifried J. Morrison · 1950
Earlier work this paper cites.
A combinatorial problem connected with differential equations
H. Davenport and A. Schinzel · 1965
Earlier work this paper cites.
Random spanning tree
A. Guenoche · 1983
Earlier work this paper cites.
Covering problems for brownian motion on spheres
Peter Matthews · 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
Charles J. Colbourn, Robert P.J. Day, and Louis D. Nel · 1989
Earlier work this paper cites.
The random walk construction of uniform spanning trees and uniform labelled trees
David J. Aldous · 1990
Earlier work this paper cites.
Sparse partitions (extended abstract)
Baruch Awerbuch and David Peleg · 1990
Earlier work this paper cites.
Generating random combinatorial objects
V. G. Kulkarni · 1990
Earlier work this paper cites.
On sparse spanners of weighted graphs
Ingo Althöfer, Gautam Das, David Dobkin, Deborah Joseph, and José Soares · 1993
Earlier work this paper cites.
The space complexity of approximating the frequency moments
Noga Alon, Yossi Matias, and Mario Szegedy · 1996
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.
Near-linear time construction of sparse neighborhood covers
Baruch Awerbuch, Bonnie Berger, Lenore Cowen, and David Peleg · 1999
Earlier work this paper cites.
Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
Frank Thomson Leighton and Satish Rao · 1999
Earlier work this paper cites.
Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions
Alexandr Andoni and Piotr Indyk · 2006
Cited alongside, same era.
Concentration inequalities and martingale inequalities: a survey
Fan Chung and Linyuan Lu · 2006
Cited alongside, same era.
Stable distributions, pseudorandom generators, embeddings, and data stream computation
Piotr Indyk · 2006
Cited alongside, same era.
Minimizing average latency in oblivious routing
Prahladh Harsha, Thomas P. Hayes, Hariharan Narayanan, Harald Räcke, and Jaikumar Radhakrishnan · 2008
Cited alongside, same era.
Graph sparsification by effective resistances
Daniel A. Spielman and Nikhil Srivastava · 2008
Cited alongside, same era.
Expanders via random spanning trees
Navin Goyal, Luis Rademacher, and Santosh Vempala · 2009
Cited alongside, same era.
Solving sdd linear systems in nearly mlog1/2n time
Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Anup B. Rao, and Shen Chen Xu · 2014
Later among the works it cites.
Approaching optimality for solving sdd linear systems
Ioannis Koutis, Gary L. Miller, and Richard Peng · 2014
Later among the works it cites.
An efficient parallel solver for sdd linear systems
Richard Peng and Daniel A. Spielman · 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.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Faster generation of random spanning trees
Jonathan A. Kelner and Aleksander Madry · 2009
Cited alongside, same era.
An o(log n/ log log n)-approximation algorithm for the asymmetric traveling salesman problem
Arash Asadpour, Michel X. Goemans, Aleksander Madry, Shayan Oveis Gharan, and Amin Saberi · 2010
Cited alongside, same era.
Graph sparsification by edge-connectivity and random spanning trees
Wai Shing Fung and Nicholas J. A. Harvey · 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.
User-friendly tail bounds for sums of random matrices
Joel A. Tropp · 2012
Cited alongside, same era.
Chip-firing games, potential theory on graphs, and spanning trees
Matthew Baker and Farbod Shokrieh · 2013
Cited alongside, same era.
Yin Tat Lee, Richard Peng, and Daniel A. Spielman · 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.
Monte carlo markov chain algorithms for sampling strongly rayleigh distributions and determinantal point processes
Nima Anari, Shayan Oveis Gharan, and Alireza Rezaei · 2016
Later among the works it cites.
Generating Random Spanning Trees via Fast Matrix Multiplication
Nicholas J. A. Harvey and Keyulu Xu · 2016
Later among the works it cites.
Approximate gaussian elimination for laplacians - fast, sparse, and simple
R. Kyng and S. Sachdeva · 2016
Later among the works it cites.
Probability on Trees and Networks
Russell Lyons and Yuval Peres · 2016
Later among the works it cites.
Sampling random spanning trees faster than matrix multiplication
David Durfee, Rasmus Kyng, John Peebles, Anup B. Rao, and Sushant Sachdeva · 2017
Closest in time.
David Durfee, John Peebles, Richard Peng, and Anup B. Rao · 2017
Closest in time.
Localization of electrical flows
Aaron Schild, Satish Rao, and Nikhil Srivastava · 2017
Closest in time.