2026-08-10T13:29:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4936 2024-03-06T10:35:35Z ddc:004 open_access

On Finding the Adams Consensus Tree Jansson, Jesper Li, Zhaoxian Sung, Wing-Kin phylogenetic tree Adams consensus centroid path wavelet tree This paper presents a fast algorithm for finding the Adams consensus tree of a set of conflicting phylogenetic trees with identical leaf labels, for the first time improving the time complexity of a widely used algorithm invented by Adams in 1972 [1]. Our algorithm applies the centroid path decomposition technique [9] in a new way to traverse the input trees' centroid paths in unison, and runs in O(k n \log n) time, where k is the number of input trees and n is the size of the leaf label set. (In comparison, the old algorithm from 1972 has a worst-case running time of O(k n^2).) For the special case of k = 2, an even faster algorithm running in O(n \cdot \frac{\log n}{\log\log n}) time is provided, which relies on an extension of the wavelet tree-based technique by Bose et al. [6] for orthogonal range counting on a grid. Our extended wavelet tree data structure also supports truncated range maximum queries efficiently and may be of independent interest to algorithm designers. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jesper Jansson and Zhaoxian Li and Wing-Kin Sung 2015 Is Part Of LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2015.487 urn:nbn:de:0030-drops-49364 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.487 eng https://creativecommons.org/licenses/by/3.0/legalcode