Generating random spanning trees more quickly than the cover time

1996/01/01 by David B. Wilson · 20 citations
Mathematics · Computer Science · Engineering · #Stochastic processes and statistical mechanics #Markov Chains and Monte Carlo Methods #Advanced Graph Theory Research #Citation #Cover (algebra) #Computer science #Spanning tree #Random access #Library science #Operations research #World Wide Web #Mathematics #Engineering #Operating system #Combinatorics

paper · pdf · doi:10.1145/237814.237880

openalex publication_date 1996/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

Introduction It is widely known how to generate random spanning trees of an undirected graph. Broder showed how at FOCS [6], and Aldous too found the algorithm [2]. Start at any vertex and do a simple random walk on the graph. Each time a vertex is first encountered, mark the edge from which it was discovered. When all the vertices are discovered, the marked edges form a random spanning tree. This algorithm is easy to code up, has small running time constants, and has a nice proof that it generates

Citations

• Graph Theory
• Exact sampling with coupled Markov chains and applications to statistical mechanics

Cited by

• Interlacements and the wired uniform spanning forest
• An SLE₂ loop measure
• Conformal invariance and 2𝐷 statistical physics
• Conformal restriction and related questions
• Conformally invariant scaling limits: an overview and a collection of problems
• Anchored burning bijections on finite and infinite graphs
• Scaling limits of loop-erased random walks and uniform spanning trees
• Conformal invariance of planar loop-erased random walks and uniform spanning trees
• The scaling limit of loop-erased random walk in three dimensions
• Near-Optimal Random Walk Sampling in Distributed Networks
• Commutation relations for Schramm‐Loewner evolutions
• Euler Integrals for Commuting SLEs
• Topology of a Uniform Spanning Tree on a Cylinder
• Does a portion of dimer configuration determines its domain of definition?
• Percolation beyond ℤd: The contributions of Oded Schramm
• Quantum Speedup for Sampling Random Spanning Trees
• Benchmarking Network Embedding Models for Link Prediction: Are We Making Progress?
• Consistency and differences between centrality measures across distinct classes of networks
• Loop-erased random walk [wikipedia]
• Spanning tree [wikipedia]