THE AGREEMENT METRIC FOR LABELED BINARY-TREES

Let S be a set of n objects. A binary tree of S is a binary tree whose leaves are labeled without repetition from S. The operation of prunin g a tree T is that of removing some leaves from T and suppressing all inner vertices of degree 2 which are formed by this deletion. Given tw o trees T and U, an agreement tree is a tree that can be obtained from T as well as from U by pruning the fewest number of leaves from the t wo trees. A quadratic algorithm is presented for doing this and two me trics are defined based on agreement trees.