We present an algorithm for calculating the quartet distance between two evolutionary trees of bounded degree on a common set of n species. The previous best algorithm has running time O(d~2 n~2) when considering trees, where no node is of more than degree d. The algorithm developed herein has running time O(d~9n log n)) which makes it the first algorithm for computing the quartet distance between non-binary trees which has a sub-quadratic worst case running time.
展开▼
