DIMACS Seminar on Math and CS in Biology

Title:

On the Agreement of Many Trees

Speaker:

Dr. Martin Farach

Dept. of Computer Science, Rutgers University

Place:

CoRE Building Room 419

Busch Campus, Rutgers University

Time:

3:00 PM

Monday, April 3, 1995

Abstract:

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