An improved algorithm for the maximum agreement subtree problem

In this paper, we solve the maximum agreement subtree problem for a set T of k rooted, leaf-labelled evolutionary trees on n leaves where T contains a binary tree. We show that the O(kn³)-time dynamic programming algorithm proposed by Farach et al. and Bryant can be implemented in O(n²log^k-1n) and O(k·n^3-(1k-1)/) using the k-dimensional binary search tree and the k-dimensional range search tree, respectively.