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

DOI10.4064/AM32-3-7zbMATH Open1138.68663OpenAlexW2078547605MaRDI QIDQ5469348FDOQ5469348

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

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

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)

Cited In (10)

• Directed forests with application to algorithms related to Markov chains
• Linking and cutting spanning trees
• Title not available (Why is that?)
• \(G\)-parking functions, acyclic orientations and spanning trees
• Liftings of tree-structured Markov chains (extended abstract)
• Title not available (Why is that?)
• A combinatorial proof of Aldous–Broder theorem for general Markov chains
• Two applications of random spanning forests
• Title not available (Why is that?)
• 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)