Generating random spanning trees more quickly than the cover time. (English) Zbl 0946.60070
Proceedings of the 28th annual ACM symposium on the theory of computing (STOC). Philadelphia, PA, USA, May 22-24, 1996. New York, NY: ACM, 296-303 (1996).
A new algorithm for generating random spanning trees is given that works for both undirected and directed graphs. The algorithm is compared to alternative algorithms presented in previous work and it is shown to be usually much faster.
For the entire collection see [Zbl 0908.00030].
For the entire collection see [Zbl 0908.00030].
Reviewer: Ove Frank (Stockholm)
MSC:
| 60J22 | Computational methods in Markov chains |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68Q25 | Analysis of algorithms and problem complexity |
| 68R10 | Graph theory (including graph drawing) in computer science |
