A combinatorial proof of Aldous–Broder theorem for general Markov chains

DOI10.1002/rsa.21101zbMath1522.05426arXiv2102.08639OpenAlexW4283163529WikidataQ113913003 ScholiaQ113913003MaRDI QIDQ6074870

Jean-François Marckert, Luis Fredes

Publication date: 19 October 2023

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2102.08639

zbMATH Keywords

matrix tree theoremrandom spanning treegolf sequences

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Connectivity (05C40) Random walks on graphs (05C81)

Cites Work

• A combinatorial approach to matrix algebra
• A reverse Aldous-Broder algorithm
• Combinatorial problems of commutation and rearrangements
• The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees
• How to Get a Perfectly Random Sample from a Generic Markov Chain and Generate a Random Spanning Tree of a Directed Graph
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A combinatorial proof of Aldous–Broder theorem for general Markov chains