Faster Algorithms for Computing the R* Consensus Tree

摘要

The fastest known algorithms for computing the R* consensus tree of k rooted phylogenetic trees with n leaves each and identical leaf label sets run in time when (Jansson and Sung in Algorithmica 66(2):329-345, 2013) and time when (Bryant in Bioconsensus, volume 61 of DIMACS series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, pp 163-184, 2003). This paper shows how to compute it in time for time for , and time for unbounded k.