Abstract
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 3 )-time dynamic programming algorithm proposed by Farach et al. and Bryant [7] can be implemented in O(n 2 log k-1 n) and O(k · n 3-1/k-1 ) using the k-dimensional binary search tree and the k-dimensional range search tree, respectively.