COMPUTING THE QUARTET DISTANCE BETWEEN EVOLUTIONARY TREES OF BOUNDED DEGREE
Martin Stig Stissing, Clara Nautrup Pedersen, Thomas Mailund, Gerth Stølting Brodal, Rolf Fagerberg · 2007
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(d2n2) when considering trees, where no node is of more than degree d. The algorithm developed herein has ranning time O(d9n log n)) which makes it the first algorithm for computing the quartet distance between non-binary trees which has a sub-quadratic worst case ranning time.