Linking and Cutting Spanning Trees

January 21, 2018 · Entered Twilight · 🏛 Algorithms

"Last commit was 5.0 years ago (≥5 year threshold)"

Evidence collected by the PWNC Scanner

Repo contents: .gitignore, K4, K5, LICENSE, LICENSE.h, README.md, Wilson.c, edgeSwap.c, graph.c, graph.h, linkCutTree.c, linkCutTree.h, makefile, mixer.c, mixer.h, randomWalk.c

Authors Luís M. S. Russo, Andreia Sofia Teixeira, Alexandre P Francisco arXiv ID 1801.06846 Category cs.DS: Data Structures & Algorithms Cross-listed cs.DM Citations 9 Venue Algorithms Repository https://github.com/LuisRusso-INESC-ID/LinkCutSpanningTrees Last Checked 1 month ago

Abstract

We consider the problem of uniformly generating a spanning tree, of a connected undirected graph. This process is useful to compute statistics, namely for phylogenetic trees. We describe a Markov chain for producing these trees. For cycle graphs we prove that this approach significantly outperforms existing algorithms. For general graphs we obtain no analytical bounds, but experimental results show that the chain still converges quickly. This yields an efficient algorithm, also due to the use of proper fast data structures. To bound the mixing time of the chain we describe a coupling, which we analyse for cycle graphs and simulate for other graphs.