Polynomial-time algorithms for the ordered maximum agreement subtree problem

Anders Dessmark, Jesper Jansson, Andrzej Lingas, Eva-Marta Lundell

    Research output: Contribution to journalArticlepeer-review

    Abstract

    For a set of rooted, unordered, distinctly leaf-labeled trees, the NP-hard maximum agreement subtree problem (MAST) asks for a tree contained (up to isomorphism or homeomorphism) in all of the input trees with as many labeled leaves as possible. We study the ordered variants of MAST where the trees are uniformly or non-uniformly ordered. We provide the first known polynomial-time algorithms for the uniformly and non-uniformly ordered homeomorphic variants as well as the uniformly and non-uniformly ordered isomorphic variants of MAST. Our algorithms run in time O(kn(3)), O (n(3) min{kn, n + log(k-1) n}), O(kn(3)), and O(n(3) min{kn, n + log(k-1) n)), respectively, where n is the number of leaf labels and k is the number of input trees.
    Original languageEnglish
    Pages (from-to)233-248
    JournalAlgorithmica
    Volume48
    Issue number3
    DOIs
    Publication statusPublished - 2007

    Subject classification (UKÄ)

    • Computer Sciences

    Free keywords

    • algorithm
    • maximum agreement subtree
    • ordered tree
    • evolutionary tree
    • time complexity

    Fingerprint

    Dive into the research topics of 'Polynomial-time algorithms for the ordered maximum agreement subtree problem'. Together they form a unique fingerprint.

    Cite this