Generating Random Spanning Trees via Fast Matrix Multiplication

Nicholas J. A. Harvey, Keyulu Xu

Type: Book-Chapter

Publication Date: 2016-01-01

Citations: 4

DOI: https://doi.org/10.1007/978-3-662-49529-2_39

View Publication

Locations

Lecture notes in computer science - View

Similar Works

Action	Title	Year	Authors
+	Sampling random spanning trees faster than matrix multiplication	2017	David Durfee Rasmus Kyng John Peebles Anup Rao Sushant Sachdeva
+	Faster generation of random spanning trees	2009	Jonathan A. Kelner Aleksander Ma̧dry
+ PDF Chat	An almost-linear time algorithm for uniform random spanning tree generation	2018	Aaron Schild
+	Sampling Random Spanning Trees Faster than Matrix Multiplication	2016	David Durfee Rasmus Kyng John Peebles Anup Rao Sushant Sachdeva
+	Sampling Random Spanning Trees Faster than Matrix Multiplication	2016	David Durfee Rasmus Kyng John Peebles Anup Rao Sushant Sachdeva
+	An almost-linear time algorithm for uniform random spanning tree generation	2017	Aaron Schild
+	An almost-linear time algorithm for uniform random spanning tree generation	2017	Aaron Schild
+ PDF Chat	Faster Generation of Random Spanning Trees	2009	Jonathan A. Kelner Aleksander Mądry
+	A note on quickly sampling a sparse matrix with low rank expectation	2017	Karl Rohe Jun Tao Xintian Han Norbert Binkiewicz
+ PDF Chat	Linear Algebraic Techniques for Spanning Tree Enumeration	2020	Steven Klee Matthew T. Stamps
+	Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple	2016	Rasmus Kyng Sushant Sachdeva
+	Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple	2016	Rasmus Kyng Sushant Sachdeva
+	Approximation of the Diagonal of a Laplacian's Pseudoinverse for Complex Network Analysis	2020	Eugenio Angriman Maria Predari Alexander van der Grinten Henning Meyerhenke
+	A note on quickly sampling a sparse matrix with low rank expectation	2018	Karl Rohe Jun Tao Xintian Han Norbert Binkiewicz
+	Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More	2016	Michael B. Cohen Jon Kelner John Peebles Richard Peng Aaron Sidford Adrian Vladu
+	Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More	2016	Michael B. Cohen Jon Kelner John Peebles Richard Peng Aaron Sidford Adrian Vladu
+ PDF Chat	Approximate Gaussian Elimination for Laplacians - Fast, Sparse, and Simple	2016	Rasmus Kyng Sushant Sachdeva
+	Approximation of the Diagonal of a Laplacian’s Pseudoinverse for Complex Network Analysis	2020	Eugenio Angriman Maria Predari Alexander van der Grinten Henning Meyerhenke
+ PDF Chat	Sparse Matrix Factorizations for Fast Linear Solvers with Application to Laplacian Systems	2017	Michael T. Schaub Maguy Tréfois Paul Van Dooren Jean‐Charles Delvenne
+	Sparse matrix factorizations for fast linear solvers with application to Laplacian systems	2017	Michael T. Schaub Maguy Tréfois Paul Van Dooren Jean‐Charles Delvenne

Works That Cite This (3)

Action	Title	Year	Authors
+ PDF Chat	A Matrix Chernoff Bound for Strongly Rayleigh Distributions and Spectral Sparsifiers from a few Random Spanning Trees	2018	Rasmus Kyng Zhao Song
+ PDF Chat	Determinant-Preserving Sparsification of SDDM Matrices with Applications to Counting and Sampling Spanning Trees	2017	David Durfee John Peebles Richard Peng Anup Rao
+	Sampling random spanning trees faster than matrix multiplication	2017	David Durfee Rasmus Kyng John Peebles Anup Rao Sushant Sachdeva

Works Cited by This (16)

Action	Title	Year	Authors
+	Probability on Trees and Networks	2016	Russell Lyons Yuval Peres
+ PDF Chat	Fast Generation of Random Spanning Trees and the Effective Resistance Metric	2014	Aleksander Ma̧dry Damian Straszak Jakub Tarnawski
+	Pipage rounding, pessimistic estimators and matrix concentration	2014	Nicholas J. A. Harvey Neil Olver
+ PDF Chat	The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees	1990	David Aldous
+	Generalized Inverses and Ranks of Block Matrices	1973	Carl D. Meyer
+	Generating random spanning trees more quickly than the cover time	1996	David B. Wilson
+	Unranking and ranking spanning trees of a graph	1989	Charles J. Colbourn Robert P.J Day Louis H. Nel
+ PDF Chat	A Randomized Rounding Approach to the Traveling Salesman Problem	2011	Shayan Oveis Gharan Amin Saberi Mohit Singh
+ PDF Chat	Triangular factorization and inversion by fast matrix multiplication	1974	James R. Bunch John E. Hopcroft
+	Generating random spanning trees	1989	Arndt Bröder