Showing 2017Show all
2 papers · 1 filter
cs.DS2017
An almost-linear time algorithm for uniform random spanning tree generation
Aaron Schild
We give an -time algorithm for generating a uniformly random spanning tree in an undirected, weighted graph with max-to-min weight ratio . We also give an $m…
cs.DS2017
Localization of Electrical Flows
Aaron Schild, Satish Rao, Nikhil Srivastava
We show that in any graph, the average length of a flow path in an electrical flow between the endpoints of a random edge is . This is a consequence of a more general…