2026-07-23T08:35:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12512 2024-03-06T10:50:19Z ddc:004 open_access

Near-Optimal Algorithm for Constructing Greedy Consensus Tree Wu, Hongxun phylogenetic trees greedy consensus trees splay tree 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 Õ(kn^1.5) [Gawrychowski, Landau, Sung, Weimann 2018] and Õ(k²n) [Sung 2019] respectively. In this paper, we improve the running time to Õ(kn). Since k input trees have Θ(kn) nodes in total, our algorithm is optimal up to polylogarithmic factors. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hongxun Wu 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.105 urn:nbn:de:0030-drops-125122 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.105 eng https://creativecommons.org/licenses/by/3.0/legalcode