Transforming rooted agreement into unrooted agreement.
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 O (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.
Przytycka
T M
TM
Department of Biophysics, Johns Hopkins School of Medicine, Baltimore, MD 21205, USA.
D000465:Algorithms; D008962:Models, Theoretical; D010802:Phylogeny