Faster Generation of Random Spanning Trees

DOI10.1109/FOCS.2009.75MaRDI QIDQ5171207zbMATH OpenOpenAlexFDO

Authors Jonathan 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 algorithms (graph-theoretic aspects) (05C85) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Graph theory (including graph drawing) in computer science (68R10)

Cited in

(17)

• 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
• Linking and cutting spanning trees
• Graph Clustering using Effective Resistance
• Derandomization beyond connectivity: undirected Laplacian systems in nearly logarithmic space
• Determinant-preserving sparsification of SDDM matrices
• Random walks, electric networks and the transience class problem of sandpiles
• Models of random subtrees of a graph
• A transient equivalence between Aldous-Broder and Wilson's algorithms and a two-stage framework for generating uniform spanning trees
• Spectral sparsification via bounded-independence sampling
• Optimal sublinear sampling of spanning trees and determinantal point processes via average-case entropic independence
• Sparsification of the regularized magnetic Laplacian with multi-type spanning forests
• Small-space spectral sparsification via bounded-independence sampling
• Sampling arborescences in parallel
• Quantum speedup for sampling random spanning trees

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5171207)