Abstract
ABSTRACT
We give a simple technique that allows to transform dynamic programming type algorithms for the Maximum Agreement Subtree problem (MAST) for rooted trees into algorithms for the Maximum Agreement Subtree problem for unrooted trees (UMAST). Using this technique we obtain an 0(n log n)-time algorithm for the UMAST problem for binary trees. This matches the complexity of the best known algorithm for the rooted case.
Get full access to this article
View all access options for this article.