An efficient algorithm for the rooted triplet distance between galled trees (Q2364900)

The authors present a faster approach for calculating the rooted triplet distance between two galled trees (a special case of phylogenetic networks in which all underlying cycles are vertex disjoint) and thus reduce the algorithm complexity from \(O(n^{2.687})\) to \(O(n\log{n})\), with \(n\) is the number of leaves. Following an overview of existing algorithms and a formal summary of concepts, the authors present the new approach based on a transformation of the input and the method developed for counting common resolved triplets and common fan triplets. For the entire collection see [Zbl 1365.92002].