A transient equivalence between Aldous-Broder and Wilson's algorithms and a two-stage framework for generating uniform spanning trees

DOI10.1016/J.DISC.2024.114285MaRDI QIDQ6646407zbMATH OpenFDO

Authors Igor Nunes, Giulio Iacobelli, Daniel R. Figueiredo

Publication date 2 December 2024

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DISC.2024.114285

zbMATH Keywords

random walktransient analysisuniform spanning treeWilson's algorithm

Mathematics Subject Classification ID

Random walks on graphs (05C81)

Recommendations

• A reverse Aldous-Broder algorithm
• An almost-linear time algorithm for uniform random spanning tree generation
• scientific article; zbMATH DE number 1256746
• Linking and cutting spanning trees
• A combinatorial proof of Aldous–Broder theorem for general Markov chains

Cites work

• A Randomized Rounding Approach to the Traveling Salesman Problem
• A self-avoiding random walk
• An \(O(\log n/\log \log n)\)-approximation algorithm for the asymmetric traveling salesman problem
• An almost-linear time algorithm for uniform random spanning tree generation
• Approaching criticality via the zero dissipation limit in the abelian avalanche model
• Bounds on the cover time
• Counting Walks and Graph Homomorphisms via Markov Chains and Importance Sampling
• Covering problems for Brownian motion on spheres
• Determinants of Laplacians on graphs
• Expander graphs and their applications
• Fast generation of random spanning trees and the effective resistance metric
• Faster Generation of Random Spanning Trees
• Generating random combinatorial objects
• Hitting times for random walks on vertex-transitive graphs
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 1256746 (Why is no real title available?)
• Introduction to algorithms.
• Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances
• Log-concave polynomials IV: approximate exchange, tight mixing times, and near-optimal sampling of forests
• Loop-erased random walks, spanning trees and Hamiltonian cycles
• Maximum hitting time for random walks on graphs
• Random spanning tree
• Random walks and the effective resistance of networks
• Sampling random spanning trees faster than matrix multiplication
• Spanning forests and the vector bundle Laplacian
• The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees
• Transfer current and pattern fields in spanning trees
• Uniform spanning forests

This page was built for publication: A transient equivalence between Aldous-Broder and Wilson's algorithms and a two-stage framework for generating uniform spanning trees

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