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

(16)

• Sparsification of the regularized magnetic Laplacian with multi-type spanning forests
• Linking and cutting spanning trees
• Engineering a combinatorial Laplacian solver: lessons learned
• Polynomial-time algorithms for submodular Laplacian systems
• Determinant-preserving sparsification of SDDM matrices
• Small-space spectral sparsification via bounded-independence sampling
• Random walks, electric networks and the transience class problem of sandpiles
• On graph parameters guaranteeing fast sandpile diffusion
• Sampling arborescences in parallel
• Graph Clustering using Effective Resistance
• Derandomization beyond connectivity: undirected Laplacian systems in nearly logarithmic space
• Spectral sparsification via bounded-independence sampling
• 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
• Optimal sublinear sampling of spanning trees and determinantal point processes via average-case entropic independence
• A queueing network-based distributed Laplacian solver

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)