## Abstract

This paper presents two sets of techniques for comparing unrooted evolutionary trees, namely, label compression and four-way dynamic programming. The technique of four-way dynamic programming transforms existing algorithms for computing rooted maximum agreement subtrees into new ones for unrooted trees. Let n be the size of the two input trees. This technique leads to an O(n log n)-time algorithm for unrooted trees whose degrees are bounded by a constant, matching the best known complexity for the rooted binary case. The technique of label compression is not based on dynamic programming. With this technique, we obtain an O(n^{1.5} log n)-time algorithm for unrooted trees with arbitrary degrees, also matching the best algorithm for the rooted unbounded degree case.

Original language | English (US) |
---|---|

Pages (from-to) | 54-65 |

Number of pages | 12 |

Journal | Conference Proceedings of the Annual ACM Symposium on Theory of Computing |

State | Published - Jan 1 1997 |

## ASJC Scopus subject areas

- Software