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

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

Probability Seminar
Mar 7, 2018, 03:10 PM - 04:00 PM | 1011 Evans Hall | Happening As Scheduled
Aaron Schild, U C Berkeley
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,...