TY - GEN

T1 - Computing the agreement of trees with bounded degrees

AU - Farach, Martin

AU - Przytycka, Teresa M.

AU - Thorup, Mikkel

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1995.

PY - 1995

Y1 - 1995

N2 - The Maximum Agreement Subtree (MAST) is a well-studied measure of similarity of leaf-labelled trees. There are several variants, depending on the number of trees, their degrees, and whether or not they are rooted. It turns out that the different variants display very different computational behavior. We address the common situation in biology, where the involved trees are rooted and of bounded degree, most typically simply being binary.— We give an algorithm which computes the MAST of к trees on n species where some tree has maximum degree d in time O(kn3 + nd). This improves the Amir and Keselman FOCS '94 O(kn d+1 + n 2d) bound. — We give an algorithm which computes the MAST of 2 trees with degree bound d in time O(n√ d.log3 n). This should be contrasted with the Farach and Thorup FOCS 94 O(nc√ logn+n√d log n) bound. Thus, for d a constant, we get an O(nlog3 n) bound, replacing the previous O(nc√log n) bound. Both of our algorithms are quite simple, relying on the combinatorial structure of the problem, rather than on advanced data structures.

AB - The Maximum Agreement Subtree (MAST) is a well-studied measure of similarity of leaf-labelled trees. There are several variants, depending on the number of trees, their degrees, and whether or not they are rooted. It turns out that the different variants display very different computational behavior. We address the common situation in biology, where the involved trees are rooted and of bounded degree, most typically simply being binary.— We give an algorithm which computes the MAST of к trees on n species where some tree has maximum degree d in time O(kn3 + nd). This improves the Amir and Keselman FOCS '94 O(kn d+1 + n 2d) bound. — We give an algorithm which computes the MAST of 2 trees with degree bound d in time O(n√ d.log3 n). This should be contrasted with the Farach and Thorup FOCS 94 O(nc√ logn+n√d log n) bound. Thus, for d a constant, we get an O(nlog3 n) bound, replacing the previous O(nc√log n) bound. Both of our algorithms are quite simple, relying on the combinatorial structure of the problem, rather than on advanced data structures.

UR - http://www.scopus.com/inward/record.url?scp=84947724965&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84947724965&partnerID=8YFLogxK

U2 - 10.1007/3-540-60313-1_157

DO - 10.1007/3-540-60313-1_157

M3 - Conference contribution

AN - SCOPUS:84947724965

SN - 3540603131

SN - 9783540603139

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 381

EP - 393

BT - Algorithms - ESA 1995 - 3rd Annual European Symposium, Proceedings

A2 - Spirakis, Paul

PB - Springer Verlag

T2 - 3rd Annual European Symposium on Algorithms, ESA 1995

Y2 - 25 September 1995 through 27 September 1995

ER -