Sampling Random Spanning Trees Faster than Matrix Multiplication

David Durfee, Rasmus Kyng, John Peebles, Anup Rao, Sushant Sachdeva

Type: Preprint

Publication Date: 2016-01-01

Citations: 0

DOI: https://doi.org/10.48550/arxiv.1611.07451

View Publication

Locations

arXiv (Cornell University) - View
DataCite API - View

Similar Works

Action	Title	Year	Authors
+	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	2017	David Durfee Rasmus Kyng John Peebles Anup Rao Sushant Sachdeva
+	Faster generation of random spanning trees	2009	Jonathan A. Kelner Aleksander Ma̧dry
+	Fast generation of random spanning trees and the effective resistance metric	2015	Aleksander Ma̧dry Damian Straszak Jakub Tarnawski
+	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
+	Generating Random Spanning Trees via Fast Matrix Multiplication	2016	Nicholas J. A. Harvey Keyulu Xu
+ PDF Chat	Fast Generation of Random Spanning Trees and the Effective Resistance Metric	2014	Aleksander Ma̧dry Damian Straszak Jakub Tarnawski
+ PDF Chat	Faster Generation of Random Spanning Trees	2009	Jonathan A. Kelner Aleksander Mądry
+	Determinant-Preserving Sparsification of SDDM Matrices with Applications to Counting and Sampling Spanning Trees	2017	David Durfee John Peebles Richard Peng Anup Rao
+	Determinant-Preserving Sparsification of SDDM Matrices with Applications to Counting and Sampling Spanning Trees	2017	David Durfee John Peebles Richard Peng Anup Rao
+ PDF Chat	An almost-linear time algorithm for uniform random spanning tree generation	2018	Aaron Schild
+ PDF Chat	Approximating Spanning Centrality with Random Bouquets	2024	Gökhan Göktürk Kamer Kaya
+ 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
+	Determinant-Preserving Sparsification of SDDM Matrices	2020	David Durfee John Peebles Richard Peng Anup Rao
+	High-precision Estimation of Random Walks in Small Space	2019	AmirMahdi Ahmadinejad Jonathan A. Kelner Jack Murtagh John Peebles Aaron Sidford Salil Vadhan
+ PDF Chat	Distributed Random Walks	2013	Atish Das Sarma Danupon Nanongkai Gopal Pandurangan Prasad Tetali
+	High-precision Estimation of Random Walks in Small Space	2019	AmirMahdi Ahmadinejad Jonathan A. Kelner Jack Murtagh John Peebles Aaron Sidford Salil Vadhan
+	A New Approach to Estimating Effective Resistances and Counting Spanning Trees in Expander Graphs	2022	Lawrence Li Sushant Sachdeva
+	Counting Triangles in Large Graphs by Random Sampling	2016	Bin Wu Ke Yi Zhenguo Li

Works That Cite This (0)

Action	Title	Year	Authors

Works Cited by This (0)

Action	Title	Year	Authors