Electronic Resource
Springer
Journal of theoretical probability
4 (1991), S. 753-766
ISSN:
1572-9230
Keywords:
Markov chain
;
stopping time
;
random graphs
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract Broder(4) has suggested a stochastic algorithm for generating a random spanning subtree of a graph. This paper studies this algorithm for a special class of graphs. A complete spectral decomposition of the associated Markov chain is given. The analysis available from this is compared to stopping-time techniques and purely geometric bounds on the second eigenvalue.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01259553
Permalink
|
Location |
Call Number |
Expected |
Availability |