# 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.