摘要：In biology, phylogenetic trees are important tools for describing evolutionary relations, but various data sources may result in conflicting phylogenetic trees. To summarize these conflicting phylogenetic trees, consensus tree methods take k conflicting phylogenetic trees (each with n leaves) as input and output a single phylogenetic tree as consensus. Among the consensus tree methods, a widely used method is the greedy consensus tree. The previous fastest algorithms for constructing a greedy consensus tree have time complexity OÌf(kn^1.5) [Gawrychowski, Landau, Sung, Weimann 2018] and OÌf(k²n) [Sung 2019] respectively. In this paper, we improve the running time to OÌf(kn). Since k input trees have Î~(kn) nodes in total, our algorithm is optimal up to polylogarithmic factors.
关键词：phylogenetic trees; greedy consensus trees; splay tree
