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

@article{JohannesFehrenbach2005,
abstract = {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 yield polynomial time mixing rates for some related Markov chains on the set of forests with roots and on the set of connected spanning subgraphs. We obtain a parametric class of stationary distributions from which we can efficiently sample. For rooted forests this includes the uniform distribution. For connected spanning subgraphs the uniform distribution is not covered.},
author = {Johannes Fehrenbach, Ludger Rüschendorf},
journal = {Applicationes Mathematicae},
keywords = {spanning trees; randomized algorithm; multicommodity flow; canonical paths; Markov chain; rooted forests; connected subgraphs},
language = {eng},
number = {3},
pages = {341-365},
title = {Analysis of Markov chain algorithms on spanning trees, rooted forests, and connected subgraphs},
url = {http://eudml.org/doc/279655},
volume = {32},
year = {2005},
}

TY - JOUR
AU - Johannes Fehrenbach
AU - Ludger Rüschendorf
TI - Analysis of Markov chain algorithms on spanning trees, rooted forests, and connected subgraphs
JO - Applicationes Mathematicae
PY - 2005
VL - 32
IS - 3
SP - 341
EP - 365
AB - 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 yield polynomial time mixing rates for some related Markov chains on the set of forests with roots and on the set of connected spanning subgraphs. We obtain a parametric class of stationary distributions from which we can efficiently sample. For rooted forests this includes the uniform distribution. For connected spanning subgraphs the uniform distribution is not covered.
LA - eng
KW - spanning trees; randomized algorithm; multicommodity flow; canonical paths; Markov chain; rooted forests; connected subgraphs
UR - http://eudml.org/doc/279655
ER -