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

DOI10.4064/AM32-3-7MaRDI QIDQ5469348zbMATH OpenOpenAlexFDO

Authors Johannes Fehrenbach, Ludger Rüschendorf

Publication date 18 May 2006

Published in Applicationes Mathematicae (Search for Journal in Brave)

Full work available at URL https://doi.org/10.4064/am32-3-7

zbMATH Keywords

Markov chainspanning treesrandomized algorithmmulticommodity flowconnected subgraphscanonical pathsrooted forests

Mathematics Subject Classification ID

Randomized algorithms (68W20) Analysis of algorithms (68W40) Deterministic network models in operations research (90B10)

Recommendations

• How to Get a Perfectly Random Sample from a Generic Markov Chain and Generate a Random Spanning Tree of a Directed Graph
• Linking and cutting spanning trees
• scientific article; zbMATH DE number 1966282
• scientific article; zbMATH DE number 953290
• Choosing a random spanning subtree: A case study

Cited in

(10)

• Directed forests with application to algorithms related to Markov chains
• Linking and cutting spanning trees
• \(G\)-parking functions, acyclic orientations and spanning trees
• scientific article; zbMATH DE number 1966282 (Why is no real title available?)
• Liftings of tree-structured Markov chains (extended abstract)
• scientific article; zbMATH DE number 2166522 (Why is no real title available?)
• A combinatorial proof of Aldous–Broder theorem for general Markov chains
• Two applications of random spanning forests
• scientific article; zbMATH DE number 6683512 (Why is no real title available?)
• Random forests and networks analysis

This page was built for publication: Analysis of Markov chain algorithms on spanning trees, rooted forests, and connected subgraphs

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