Computing the agreement of trees with bounded degrees

Martin Farach, Teresa M. Przytycka, Mikkel Thorup

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    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.

    Original languageEnglish (US)
    Title of host publicationAlgorithms - ESA 1995 - 3rd Annual European Symposium, Proceedings
    EditorsPaul Spirakis
    PublisherSpringer Verlag
    Number of pages13
    ISBN (Print)3540603131, 9783540603139
    StatePublished - 1995
    Event3rd Annual European Symposium on Algorithms, ESA 1995 - Corfu, Greece
    Duration: Sep 25 1995Sep 27 1995

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    Other3rd Annual European Symposium on Algorithms, ESA 1995

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science


    Dive into the research topics of 'Computing the agreement of trees with bounded degrees'. Together they form a unique fingerprint.

    Cite this