An improved algorithm for the maximum agreement subtree problem

[[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(kn3)-time dynamic programming algorithm proposed by Farach et al. and Bryant [7] can be implemented in O(n2logk-1n) and O(k · n3-1/k-1) using the k-dimensional binary search tree and the k-dimensional range search tree, respectively.[[fileno]]2030209030005[[department]]資訊工程學