Linking and Cutting Spanning Trees

descriptionPublicationkeyboard_double_arrow_right Article , Preprint , Other literature type 19 Apr 2018Embargo end date: 01 Jan 2018 English Publisher:MDPI AGJournal:Algorithms, volume 11, page 53 (eissn: 1999-4893,

Copyright policy )Funded by:FCT | Instituto de Engenharia d..., EC | BIRDS

Authors: Luís M. S. Russo; Andreia Sofia Teixeira; Alexandre P. Francisco;

doi: 10.3390/a11040053 , 10.48550/arxiv.1801.06846

arXiv: 1801.06846

Linking and Cutting Spanning Trees

- Summary
- Subjects
- Metrics

Abstract

We consider the problem of uniformly generating a spanning tree for an undirected connected graph. This process is useful for computing 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, experimental results show that the chain converges quickly. This yields an efficient algorithm due to the use of proper fast data structures. To obtain the mixing time of the chain we describe a coupling, which we analyze for cycle graphs and simulate for other graphs.

Related Organizations

Universidade Nova de Lisboa
Portugal
University of Lisbon
Universidade de Lisboa
Portugal
Instituto Superior Técnico, Universidade de Lisboa
Portugal
Universidade de Lisboa
Portugal

View all View all

Keywords

FOS: Computer and information sciences, spanning tree, Discrete Mathematics (cs.DM), Industrial engineering. Management engineering, Markov chain, QA75.5-76.95, T55.4-60.8, Markov chains (discrete-time Markov processes on discrete state spaces), mixing time, Random walks on graphs, Electronic computers. Computer science, Graph algorithms (graph-theoretic aspects), Computational methods in Markov chains, Computer Science - Data Structures and Algorithms, uniform generation, Numerical analysis or methods applied to Markov chains, Data Structures and Algorithms (cs.DS), link-cut tree, Computer Science - Discrete Mathematics

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	6
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Top 10%
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average