Faster Generation of Random Spanning Trees

DOI10.1109/FOCS.2009.75zbMath1292.05248OpenAlexW2109176946MaRDI QIDQ5171207

Jonathan A. Kelner, Aleksander Mądry

Publication date: 25 July 2014

Published in: 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/focs.2009.75

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (10)

Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space ⋮ Models of random subtrees of a graph ⋮ Determinant-Preserving Sparsification of SDDM Matrices ⋮ Graph Clustering using Effective Resistance ⋮ Engineering a combinatorial Laplacian solver: lessons learned ⋮ A queueing network-based distributed Laplacian solver ⋮ Polynomial-time algorithms for submodular Laplacian systems ⋮ On graph parameters guaranteeing fast sandpile diffusion ⋮ Random Walks, Electric Networks and The Transience Class problem of Sandpiles ⋮ Linking and cutting spanning trees

This page was built for publication: Faster Generation of Random Spanning Trees