TY - JOUR
T1 - General techniques for comparing unrooted evolutionary trees
AU - Kao, Ming Yang
AU - Lam, Tak Wah
AU - Przytycka, Teresa M.
AU - Sung, Wing Kin
AU - Ting, Hing Fung
PY - 1997
Y1 - 1997
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0030642910&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0030642910&partnerID=8YFLogxK
U2 - 10.1145/258533.258550
DO - 10.1145/258533.258550
M3 - Conference article
AN - SCOPUS:0030642910
SN - 0734-9025
SP - 54
EP - 65
JO - Conference Proceedings of the Annual ACM Symposium on Theory of Computing
JF - Conference Proceedings of the Annual ACM Symposium on Theory of Computing
T2 - Proceedings of the 1997 29th Annual ACM Symposium on Theory of Computing
Y2 - 4 May 1997 through 6 May 1997
ER -