Wilson, David Bruce 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]. Reviewer: Ove Frank (Stockholm) Cited in 3 ReviewsCited in 138 Documents 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 Keywords:graphic algorithms; spanning tree; random trees; random rooted trees PDFBibTeX XMLCite \textit{D. B. Wilson}, in: Proceedings of the 28th annual ACM symposium on the theory of computing, STOC '96. Philadelphia, PA, USA, May 22--24, 1996. New York, NY: ACM. 296--303 (1996; Zbl 0946.60070)