The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees
From MaRDI portal
Publication:3204479
DOI10.1137/0403039zbMath0717.05028OpenAlexW1985234177MaRDI QIDQ3204479
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
Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Combinatorial probability (60C05)
Related Items (69)
Random walks, totally unimodular matrices, and a randomised dual simplex algorithm ⋮ Distribution of tree parameters by martingale approach ⋮ Multi-Eulerian tours of directed graphs ⋮ Diameter of random spanning trees in a given graph ⋮ The distribution of height and diameter in random non-plane binary trees ⋮ Determinantal probability measures ⋮ Surprising identities for the greedy independent set on Cayley trees ⋮ Convergence in distribution of random metric measure spaces (\(\Lambda \)-coalescent measure trees) ⋮ On the number of broadcast schemes in networks ⋮ Tree/endofunction bijections and concentration inequalities ⋮ Fundamental constants in the theory of two-dimensional uniform spanning trees ⋮ Recent developments and problems in the domain of random generation ⋮ Are crossing dependencies really scarce? ⋮ Random-cluster measures and uniform spanning trees ⋮ Branching Processes -- A General Concept ⋮ The diameter of uniform spanning trees in high dimensions ⋮ How to couple from the past using a read-once source of randomness ⋮ On combinatorial testing problems ⋮ On the expansion of combinatorial polytopes ⋮ The local weak limit of 𝑘-dimensional hypertrees ⋮ On distance graph coloring problems ⋮ The Moran forest ⋮ A combinatorial proof of Aldous–Broder theorem for general Markov chains ⋮ How to generate perfect mazes? ⋮ Improved methods to compare distance metrics in networks using uniform random spanning trees (DIMECOST) ⋮ The Foata-Fuchs proof of Cayley's formula, and its probabilistic uses ⋮ The number and degree distribution of spanning trees in the Tower of Hanoi graph ⋮ Almost triangular Markov chains on \(\mathbb{N}\) ⋮ Random interlacement is a factor of i.i.d. ⋮ Logarithmic corrections to scaling in the four-dimensional uniform spanning tree ⋮ Methods for determining cycles of a specific length in undirected graphs with edge weights ⋮ Models of random subtrees of a graph ⋮ Spanning tree bounds for grid graphs ⋮ Interactions of computational complexity theory and mathematics ⋮ On a wider class of prior distributions for graphical models ⋮ Determinant-Preserving Sparsification of SDDM Matrices ⋮ Codes and noncommutative stochastic matrices ⋮ Percolation beyond \(\mathbb Z^{d}\): the contributions of Oded Schramm ⋮ Perfect sampling methods for random forests ⋮ Edge crossings in random linear arrangements ⋮ Graph Clustering using Effective Resistance ⋮ A general framework for nonequilibrium phenomena: The master equation and its formal consequences. ⋮ Cutting down trees with a Markov chainsaw ⋮ Asymptotic height distribution in high-dimensional sandpiles ⋮ The scaling window of the 2-SAT transition ⋮ Shuffling biological sequences with motif constraints ⋮ 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 ⋮ A queueing network-based distributed Laplacian solver ⋮ Interlacements and the wired uniform spanning forest ⋮ Generalized loop‐erased random walks and approximate reachability ⋮ Counting trees with random walks ⋮ Navigation in spatial networks: a survey ⋮ Shuffling biological sequences ⋮ CoEulerian graphs ⋮ Universality of high-dimensional spanning forests and sandpiles ⋮ A reverse Aldous-Broder algorithm ⋮ Random walks with local memory ⋮ RANDOM COMPLEXES AND ℓ2-BETTI NUMBERS ⋮ Infinite-step stationarity of rotor walk and the wired spanning forest ⋮ Non-uniform random spanning trees on weighted graphs ⋮ Exact Goodness‐of‐Fit Tests for Markov Chains ⋮ Scaling limits of loop-erased random walks and uniform spanning trees ⋮ Linking and cutting spanning trees ⋮ Random Walks and Quantum Gravity in Two Dimensions ⋮ A conversation with David J. Aldous ⋮ Watermelons on the half-plane ⋮ Rayleigh processes, real trees, and root growth with re-grafting
This page was built for publication: The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees
