TY - GEN

T1 - Polynomial-time algorithms for the ordered maximum agreement subtree problem

AU - Dessmark, Anders

AU - Jansson, Jesper Andreas

AU - Lingas, Andrzej

AU - Lundell, Eva Marta

PY - 2004

Y1 - 2004

N2 - 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-1n), O(kn 3), and O(n 3 min kn, {n+ log k-2n}), respectively, where n is the number of leaf labels and k is the number of input trees.

AB - 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-1n), O(kn 3), and O(n 3 min kn, {n+ log k-2n}), respectively, where n is the number of leaf labels and k is the number of input trees.

KW - Algorithm

KW - Evolutionary tree

KW - Maximum agreement subtree

KW - Ordered tree

KW - Time complexity

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-35048884602&origin=resultslist&sort=plf-f&src=s&sid=b47907a065552896d4c454b2954d2d8a&sot=autdocs&sdt=autdocs&sl=18&s=AU-ID%2810439175200%29&relpos=97&citeCnt=3&searchTerm=

U2 - 10.1007/s00453-007-0080-9

DO - 10.1007/s00453-007-0080-9

M3 - Conference article published in proceeding or book

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 220

EP - 229

BT - Combinatorial Pattern Matching, 15th Annual Symposium, CPM 2004, Istanbul, Turkey, July 2004 Proceedings

A2 - Cenk Sahinalp , Suleyman

A2 - Muthukrishnan , S.

A2 - Dogrusoz , Ugur

T2 - 15th Annual Symposium on Combinatorial Pattern Matching, CPM 2004

Y2 - 5 July 2004 through 7 July 2004

ER -