Choosing a random spanning subtree: a case study |
| |
| Authors: | Richard Stong |
| |
| Affiliation: | (1) Department of Mathematics, Harvard University, 02138 Cambridge, Massachusetts;(2) Present address: Department of Mathematics, University of California, 90024 Los Angeles |
| |
| 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. |
| |
| Keywords: | Markov chain stopping time random graphs |
| 本文献已被 SpringerLink 等数据库收录！ |
