Polynomial-time algorithms for the ordered maximum agreement subtree problem
Författare
Summary, in English
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.
Avdelning/ar
- Computer Science
Publiceringsår
2007
Språk
Engelska
Sidor
233-248
Publikation/Tidskrift/Serie
Algorithmica
Volym
48
Issue
3
Dokumenttyp
Artikel i tidskrift
Förlag
Springer
Ämne
- Computer Science
Nyckelord
- algorithm
- maximum agreement subtree
- ordered tree
- evolutionary tree
- time complexity
Status
Published
Projekt
- VR 2005-4085
ISBN/ISSN/Övrigt
- ISSN: 0178-4617