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-labeled evolutionary trees on n leaves where T contains a binary tree. We show that the O(kn(3))-time dynamic-programming algorithm proposed by Bryant [Building trees, hunting for trees, and comparing trees: theory and methods in phylogenetic analysis, Ph.D. thesis, Dept. Math., University of Canterbury, 1997, pp. 174-182] can be implemented in O(kn(2) +n(2)log(k-2)n log log n) and O(kn(3-1/(k-1))) time by using multidimensional range search related data structures proposed by Gabow et al. [Scaling and related techniques for geometry problems, in: Proc. 16th Annual ACM Symp. on Theory of Computing, 1984, pp. 135-143] and Bentley [Multidimensional binary search trees in database applications, IEEE Trans. Softw. Eng. SE-5 (4) (1979) 333-340], respectively. When k &LT; 2 + (log n - log log log n)/(log log n), the first implementation will be significantly faster than Bryant's algorithm. For k = 3, it yields the best known algorithm which runs in O(n(2) log n log log n)-time. &COPY; 2005 Elsevier B.V. All rights reserved.
maximum agreement subtree evolutionary tree multidimensional binary search tree design of algorithms leaf-labeled tree multidimensional range search tree