David Bruce Wilson developed an exact sampling algorithm for uniform spanning trees. Wilson's algorithm grows a tree by adding loop-erased random walks, each stopped on first reaching the tree already constructed.[ref]
Generating Random Spanning Trees More Quickly than the Cover Time by David Bruce Wilson. Original byline, RandomTreeWithRoot and correctness argument
Erasing loops ensures that an added path creates no cycle. The more surprising assertion is distributional: the resulting tree is uniform among spanning trees, despite the sequential construction and the choice of starting vertices. The algorithm makes a global random combinatorial object accessible through local walk operations.[ref]
Articles by others on the same topic
There are currently no matching articles.