A reverse Aldous/Broder algorithm
| Autor: | Hu, Yiping, Lyons, Russell, Tang, Pengfei |
|---|---|
| Rok vydání: | 2019 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | The Aldous--Broder algorithm provides a way of sampling a uniformly random spanning tree for finite connected graphs using simple random walk. Namely, start a simple random walk on a connected graph and stop at the cover time. The tree formed by all the first-entrance edges has the law of a uniform spanning tree. Here we show that the tree formed by all the last-exit edges also has the law of a uniform spanning tree. This answers a question of Tom Hayes and Cris Moore from 2010. The proof relies on a bijection that is related to the BEST theorem in graph theory. We also give other applications of our results, including new proofs of the reversibility of loop-erased random walk, of the Aldous--Broder algorithm itself, and of Wilson's algorithm. Comment: 14 pages, 1 figure |
| Databáze: | arXiv |
| Externí odkaz: |
|