David Bruce Wilson
- 1.David Aldous. On simulating a Markov chain stationary distribution when transition probabilities are unknown, 1994. Preprint.Google Scholar
- 2.David J. Aldous. A random walk construction of uniform spanning trees and uniform labelled trees. SIAM Journal of Discrete Mathematics, 3(4):450- 465, 1990. Google ScholarDigital Library
- 3.David J. Aldous and James A. Fill. Reversible Markov Chains and Random Walks on Graphs. Book in preparation, 1995.Google Scholar
- 4.S0ren Asmussen, Peter W. Glynn, and Hermann Thorisson. Stationary detection in the initial transient problem. A CM Transactions on Modeling and Computer Simulation, 2(2):130-157, 1992. Google ScholarDigital Library
- 5.B~la Bollob~s. Graph Theory: An Introductory Course. Springer-Verlag, 1979. Graduate texts in mathematics, ~63.Google Scholar
- 6.Andrei Broder. Generating random spanning trees. in Foundations of Computer Science, pages 442- 447, 1989.Google Scholar
- 7.Robert Burton and Robin Pemantle. Local characteristics, entropy and limit theorems for spanning trees and domino filings via transfer-impedances. The Annals of Probability, 21(3):1329-1371, 1993.Google ScholarCross Ref
- 8.Charles J. Colbourn, Robert P. J. Day, and Louis D. Nel. Unranking and ranking spanning trees of a graph. Journal o/Algorithms, 10:271- 286, 1989. Google ScholarDigital Library
- 9.Charles J. Colbourn, Bradley M. Debroni, and Wendy J. Myrvold. Estimating the coefficients of the reliability polynomial. Congressus Numerantium, 62:217-223, 1988.Google Scholar
- 10.Charles J. Colbourn, Wendy J. Myrvold, and Eugene Neufeld. Two algorithms for unranking arborescences. Journal of Algorithms, 1995. To appear. Google ScholarDigital Library
- 11.Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9:251-280, 1990. Google ScholarDigital Library
- 12.Persi Diaconis. Group Representations in Probability and Statistics. Institute of Mathematical Statistics, 1988.Google Scholar
- 13.Persi Diaconis and Laurent Saloff-Coste. What do we know about the Metropolis algorithm? In Symposium on the Theory of Computing, pages 112- 129, 1995. Google ScholarDigital Library
- 14.Persi Diaconis and Daniel Stroock. Geometric bounds for eigenvalues of Markov chains. The Annals of Applied Probability, 1(1):36-61, 1991.Google ScholarCross Ref
- 15.James A. Fill, 1995. Personal communication.Google Scholar
- 16.A. Gudnoche. Random spanning tree. Journal of Algorithms, 4:214-220, 1983. In French.Google ScholarCross Ref
- 17.Mark Jerrum and Alistair Sinclair. Approximating the permanent. SIAM Journal on Computing, 18(6):1149-1178, 1989. Google ScholarDigital Library
- 18.D. Kandel, Y. Matias, R. Unger, and P. Winkler. Shuffling biological sequences, 1995. Pteprint.Google Scholar
- 19.V. G. Kulkarni. Generating random combinatorim objects. Journal of Algorithms, 11 (2):185-207, 1990. Google ScholarDigital Library
- 20.Gregory F. Lawler. Intersections of Random Walks. Birkh&user, 1991.Google Scholar
- 21.Liszl6 Lov~sz and Mikl6s Simonovits. ,On the randomized complexity of volume and diameter. In Foundations of Computer Science, pages 482-491, 1992.Google Scholar
- 22.L~szl6 Lov~sz and Peter Winkler. Exact mixing in an unknown Markov chain. Electronic Journal of Combinatorics, 2, 1995. Paper #R15.Google Scholar
- 23.Robin Pemantle. Choosing a spanning tree for the integer lattice uniformly. The Annals o} Probabihty, 19(4):1559-1574, 1991.Google Scholar
- 24.James G. Propp and David B. Wilson. Exact sampiing with coupled Markov chains and applications to statistical mechanics. Random Structures and Algorithms, 1996. To appear. Google ScholarDigital Library
- 25.Alistair Sinclair. Algorithms for Random Generation and Counting: A Markov Chain Approach. Birkh~user, 1993. Google ScholarDigital Library
- 26.David B. Wilson and James G. Propp. How to get an exact sample from a generic Markov chain and sample a random spanning tree from a directed graph, both within the cover time. In Symposium on Discrete Algorzthms, 1996. Google ScholarDigital Library
Index Terms
- Generating random spanning trees more quickly than the cover time
Recommendations
Generating random spanning trees
SFCS '89: Proceedings of the 30th Annual Symposium on Foundations of Computer ScienceThe author describes a probabilistic algorithm that, given a connected, undirected graph G with n vertices, produces a spanning tree of G chosen uniformly at random among the spanning trees of G. The expected running time is O(n log n) per generated ...
Low-Degree Spanning Trees of Small Weight
Given $n$ points in the plane, the degree-$K$ spanning-tree problem asks for a spanning tree of minimum weight in which the degree of each vertex is at most $K$. This paper addresses the problem of computing low-weight degree-$K$ spanning trees for $K>2$...
Balancing minimum spanning trees and multiple-source minimum routing cost spanning trees on metric graphs
Both the building cost and the multiple-source routing cost are important considerations in construction of a network system. A spanning tree with minimum building cost among all spanning trees is called a minimum spanning tree (MST), and a spanning ...
Comments