论文标题
Aldous-Broder和Wilson的算法与生成统一树木的均匀框架之间的瞬态等效性
A transient equivalence between Aldous-Broder and Wilson's algorithms and a two-stage framework for generating uniform spanning trees
论文作者
论文摘要
$ aldous \ text { - } broder $和$ wilson $是两种著名的算法，以基于随机步道生成统一跨越树（USTS）的算法。这项工作研究了他们的关系，同时他们建造随机树，目的是减少建造生成树所需的总时间。使用$ branches $ - $ - $ - $ - $ - $ - $ - $ - $ - $ - 在特定停止时间产生的概念，我们表明，在完整图上运行时，在这些停止时间上运行时，两种算法在完整图上运行时建立的树是统计上等效的。这导致了一种混合算法，该算法可以比两种算法中的任何一个都更快地生成完整图的统一树。还提出了一个有效的两阶段框架，以探索超出完整图的混合方法，显示了其在各种示例中的可行性，包括及时图表，其中它需要比$ wilson $少25％的时间来生成UST。
The $Aldous\text{-}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.
