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