zbMATH — the first resource for mathematics

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].

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