An almost-linear time algorithm for uniform random spanning tree generation

Probability Seminar
Mar 7, 2018 3:10pm to 4:00pm
Location: 
1011 Evans Hall
Status: 
Happening As Scheduled
We give an m^{1+o(1)} beta^{o(1)}-time algorithm for generating uniformly random spanning trees in weighted graphs with max-to-min weight ratio beta. In the process, we illustrate how fundamental tradeoffs in graph partitioning can be overcome by eliminating vertices from a graph using Schur complements of the associated Laplacian matrix. Our starting point is the Aldous-Broder algorithm,...
Aaron Schild, U C Berkeley