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.


dimacs-www@dimacs.rutgers.edu
Document last modified on March 28, 1995