DIMACS Seminar on Math and CS in Biology


Transforming Rooted Agreement Subtree Algorithms into Unrooted Agreement


Teresa Przytycka
Johns Hopkins University


Seminar Room 431, CoRE Building
Rutgers University.


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

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