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(n1.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