TY - GEN
T1 - Polynomial-time algorithms for the ordered maximum agreement subtree problem
AU - Dessmark, Anders
AU - Jansson, Jesper
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{nk, n + log (k-->1) n}), O(kn(3)), and O((k + n)n(3)), 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{nk, n + log (k-->1) n}), O(kn(3)), and O((k + n)n(3)), respectively, where n is the number of leaf labels and k is the number of input trees.
U2 - 10.1007/s00453-007-0080-9
DO - 10.1007/s00453-007-0080-9
M3 - Paper in conference proceeding
SN - 3-540-22341-X
VL - 3109
SP - 220
EP - 229
BT - Combinatorial pattern matching / Lecture notes in computer science
PB - Springer
T2 - 15th Annual Symposium, CPM 2004
Y2 - 5 July 2004 through 7 July 2004
ER -