The Maximum Agreement Subtree (MAST) is a well-studied
measure of similarity of leaf-labelled trees. There are several
variants, depending on the number of trees, their degrees, and whether
or not they are rooted. It turns out that the different variants
display very different computational behavior. We address the common
situation in biology, where the involved trees are rooted and of bounded
degree, most typically simply being binary.
We give an algorithm which computes the MAST of $k$ trees on
$n$ species where some tree has maximum degree $d$ in time
$O(kn^3+n^d)$. This improves the Amir and Keselman FOCS '94
$O(kn^{d+1}+n^{2d})$ bound. This algorithm has been impelmented
as a part of the PAUP sftware package.
We give an algorithm which computes the MAST of 2 trees with
degree bound $d$ in time $O(n\sqrt{d}\log^3 n)$.
Both of our algorithms are quite simple, relying on the combinatorial
structure of the problem, rather than on advanced data structures.
This is a joint work with Martin Farach (Rutgers) and Mikkel Thorup
(Copenhagen).