The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees

DOI10.1137/0403039zbMATH Open0717.05028OpenAlexW1985234177MaRDI QIDQ3204479FDOQ3204479

David Aldous

Publication date: 1990

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/e719d335adf1250c79a6a0e399145ce96aa17b03

Recommendations

• scientific article; zbMATH DE number 953290
• How to Get a Perfectly Random Sample from a Generic Markov Chain and Generate a Random Spanning Tree of a Directed Graph
• Non-uniform random spanning trees on weighted graphs
• scientific article; zbMATH DE number 1195780
• Loop-erased random walks, spanning trees and Hamiltonian cycles

zbMATH Keywords

random walkuniform random spanning tree

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Combinatorial probability (60C05)

Cited In (79)

• The number and degree distribution of spanning trees in the Tower of Hanoi graph
• Random walks with local memory
• On combinatorial testing problems
• Asymptotic height distribution in high-dimensional sandpiles
• Linking and cutting spanning trees
• Random walks, totally unimodular matrices, and a randomised dual simplex algorithm
• On the number of broadcast schemes in networks
• Multi-Eulerian tours of directed graphs
• Interlacements and the wired uniform spanning forest
• Random Walks and Quantum Gravity in Two Dimensions
• Counting trees with random walks
• Navigation in spatial networks: a survey
• Scaling limits of loop-erased random walks and uniform spanning trees
• Generalized loop‐erased random walks and approximate reachability
• Logarithmic corrections to scaling in the four-dimensional uniform spanning tree
• On the expansion of combinatorial polytopes
• Non-uniform random spanning trees on weighted graphs
• Tree/endofunction bijections and concentration inequalities
• Loop-erased random walk branch of uniform spanning tree in topological polygons
• Determinantal probability measures
• How to couple from the past using a read-once source of randomness
• RANDOM COMPLEXES AND ℓ²-BETTI NUMBERS
• Fundamental constants in the theory of two-dimensional uniform spanning trees
• Are crossing dependencies really scarce?
• Graph Clustering using Effective Resistance
• On distance graph coloring problems
• Universality of high-dimensional spanning forests and sandpiles
• Title not available (Why is that?)
• Cutting down trees with a Markov chainsaw
• The Moran forest
• The diameter of uniform spanning trees in high dimensions
• A combinatorial proof of Aldous–Broder theorem for general Markov chains
• Models of random subtrees of a graph
• Diameter of random spanning trees in a given graph
• Convergence in distribution of random metric measure spaces (\(\Lambda \)-coalescent measure trees)
• Choosing a random spanning subtree: A case study
• Approximation of the Diagonal of a Laplacian’s Pseudoinverse for Complex Network Analysis
• The scaling of the minimum sum of edge lengths in uniformly random trees
• Recent developments and problems in the domain of random generation
• CoEulerian graphs
• A conversation with David J. Aldous
• Shuffling biological sequences
• Percolation beyond \(\mathbb Z^{d}\): the contributions of Oded Schramm
• Title not available (Why is that?)
• Codes and noncommutative stochastic matrices
• Exact goodness-of-fit tests for Markov chains
• Branching Processes -- A General Concept
• Rayleigh processes, real trees, and root growth with re-grafting
• Shuffling biological sequences with motif constraints
• Determinant-Preserving Sparsification of SDDM Matrices
• Loop-erased random walks, spanning trees and Hamiltonian cycles
• Perfect sampling methods for random forests
• Random-cluster measures and uniform spanning trees
• A queueing network-based distributed Laplacian solver
• The distribution of height and diameter in random non-plane binary trees
• A reverse Aldous-Broder algorithm
• A general framework for nonequilibrium phenomena: The master equation and its formal consequences.
• The scaling window of the 2-SAT transition
• Almost triangular Markov chains on \(\mathbb{N}\)
• Infinite-step stationarity of rotor walk and the wired spanning forest
• Random interlacement is a factor of i.i.d.
• Watermelons on the half-plane
• Edge crossings in random linear arrangements
• Distribution of tree parameters by martingale approach
• Methods for determining cycles of a specific length in undirected graphs with edge weights
• Logarithmic corrections to the Alexander-Orbach conjecture for the four-dimensional uniform spanning tree
• Spanning tree bounds for grid graphs
• Interactions of computational complexity theory and mathematics
• On a wider class of prior distributions for graphical models
• Spectral Clustering, Bayesian Spanning Forest, and Forest Process
• Coboundary expansion for the union of determinantal hypertrees
• The local weak limit of 𝑘-dimensional hypertrees
• A transient equivalence between Aldous-Broder and Wilson's algorithms and a two-stage framework for generating uniform spanning trees
• How to generate perfect mazes?
• Improved methods to compare distance metrics in networks using uniform random spanning trees (DIMECOST)
• Surprising identities for the greedy independent set on Cayley trees
• A Telescopic Proof of Cayley’s Formula
• Parallel discrete sampling via continuous walks
• The Foata-Fuchs proof of Cayley's formula, and its probabilistic uses

This page was built for publication: The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3204479)