2022/06/24 by Igor Nunes, Nunes, Igor, Giulio Iacobelli +3
Computer Science · Mathematics · #Advanced Database Systems and Queries #Combinatorics (math.CO) #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR) #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.2206.12378
openalex publication_date 2022/06/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Aldous-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.