DIMACS Seminar on Math and CS in Biology


Title:

Transforming Rooted Agreement Subtree Algorithms into Unrooted Agreement

Speaker:

Teresa Przytycka
Johns Hopkins University

Place:

Seminar Room 431, CoRE Building
Rutgers University.

Time:

11:00 a.m.
Thursday, February 27, 1997
Abstract:

We give a simple technique that allows us to transform dynamic programming types of algorithms for the Maximum Agreement Subtree problem for rooted trees (MAST) into algorithms for Maximum Agreement Subtree for the unrooted version of the problem (UMAST). Using this technique, we obtain an $O(n \log n)$ time algorithm for the UMAST problem for binary (or bounded degree) trees. This matches the complexity of the best known algorithms for the rooted case.


Document last modified on February 21, 1997