Generating Random Spanning Trees

The author describes a probabilistic algorithm that, given a connected, undirected graph G with n vertices, produces a spanning tree of G chosen uniformly at random among the spanning trees of G. The expected running time is O(n log n) per generated tree for almost all graphs, and O(n/sup 3/) for the worst graphs. Previously known deterministic algorithms are much more complicated and require O(n/sup 3/) time per generated tree. A Markov chain is called rapidly mixing if it gets close to the limit distribution in time polynomial in the log of the number of states. Starting from the analysis of the above algorithm, it is shown that the Markov chain on the space of all spanning trees of a given graph where the basic step is an edge swap is rapidly mixing. >

Authors

• Andrei Z. Broder

Keywords

• Tree graphs
• Polynomials
• Algorithm design and analysis
• Ice
• Stochastic processes
• Eigenvalues and eigenfunctions
• Graph theory
• Spanning Tree
• Markov Chain
• Running Time
• State Space
• Undirected
• Random Walk
• Stationary Distribution
• Directed Graph
• Root Of The Tree
• Transition Probability Matrix
• Regular Graphs
• Current Tree
• Simple Random Walk