Displaying similar documents to “Mixing time for a random walk on rooted trees.”

Analysis of Markov chain algorithms on spanning trees, rooted forests, and connected subgraphs

Johannes Fehrenbach, Ludger Rüschendorf (2005)

Applicationes Mathematicae

Similarity:

We analyse a natural edge exchange Markov chain on the set of spanning trees of an undirected graph by the method of multicommodity flows. The analysis is then refined to obtain a canonical path analysis. The construction of the flow and of the canonical paths is based on related path constructions in a paper of Cordovil and Moreira (1993) on block matroids. The estimates of the congestion measure imply a polynomial bound on the mixing time. The canonical paths for spanning trees also...