A transient equivalence between Aldous-Broder and Wilson's algorithms and a two-stage framework for generating uniform spanning trees

arXiv2206.12378MaRDI QIDQ6403080FDOQ6403080

Authors: Igor Nunes, Giulio Iacobelli, Daniel R. Figueiredo 

Publication date: 24 June 2022

Abstract: The $Aldousext-Broder$ and $Wilson$ are two well-known algorithms to generate uniform spanning trees (USTs) based on random walks. This work studies their relationship while they construct random trees with the goal of reducing the total time required to build the spanning tree. Using the notion of $branches$ $-$ paths generated by the two algorithms on particular stopping times, we show that the trees built by the two algorithms when running on a complete graph are statistically equivalent on these stopping times. This leads to a hybrid algorithm that can generate uniform spanning trees of complete graphs faster than either of the two algorithms. An efficient two-stage framework is also proposed to explore this hybrid approach beyond complete graphs, showing its feasibility in various examples, including transitive graphs where it requires 25% less time than $Wilson$ to generate a UST.

This page was built for publication: A transient equivalence between Aldous-Broder and Wilson's algorithms and a two-stage framework for generating uniform spanning trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6403080)