On the agreement of many trees

Martin Farach, Teresa M. Przytycka, Mikkel Thorup

    Research output: Contribution to journalArticlepeer-review


    We consider the problem of computing the Maximum Agreement Subtree (MAST) of a set of rooted leaf labeled trees. We give an algorithm which computes the MAST of k trees on n leaves where some tree has maximum outdegree d in time O(kn3 + nd).

    Original languageEnglish (US)
    Pages (from-to)297-301
    Number of pages5
    JournalInformation Processing Letters
    Issue number6
    StatePublished - Sep 29 1995


    • Analysis
    • Computational biology
    • Design of algorithms
    • Phylogentic trees

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Signal Processing
    • Information Systems
    • Computer Science Applications


    Dive into the research topics of 'On the agreement of many trees'. Together they form a unique fingerprint.

    Cite this