DIMACS Seminar on Math and CS in Biology


On the Agreement of Many Trees


Dr. Martin Farach
Dept. of Computer Science, Rutgers University


CoRE Building Room 419
Busch Campus, Rutgers University


3:00 PM
Monday, April 3, 1995


We consider the problem of computing the {\em Maximum Agreement Subtree (MAST)} of a set of leaf labeled trees. 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 (1994/1995) $O(kn^{d+1}+n^{2d})$ bound. Our algorithm is very simple and has been implemented as part of the next release of the PAUP software package.

Joint work with Teresa M. Przytycka and Mikkel Thorup.

Document last modified on March 28, 1995