Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Polynomial-time algorithms for the ordered maximum agreement subtree problem

Dessmark, Anders LU ; Jansson, Jesper LU ; Lingas, Andrzej LU and Lundell, Eva-Marta LU (2007) In Algorithmica 48(3). p.233-248
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.
Please use this url to cite or link to this publication:
author
; ; and
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
algorithm, maximum agreement subtree, ordered tree, evolutionary tree, time complexity
in
Algorithmica
volume
48
issue
3
pages
233 - 248
publisher
Springer
external identifiers
  • wos:000247872000002
  • scopus:34547253932
ISSN
0178-4617
DOI
10.1007/s00453-007-0080-9
project
VR 2005-4085
language
English
LU publication?
yes
id
172e2b11-8c84-461d-8e41-38a3761a2a5b (old id 646040)
date added to LUP
2016-04-01 12:20:17
date last changed
2025-04-04 14:04:03
@article{172e2b11-8c84-461d-8e41-38a3761a2a5b,
  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.}},
  author       = {{Dessmark, Anders and Jansson, Jesper and Lingas, Andrzej and Lundell, Eva-Marta}},
  issn         = {{0178-4617}},
  keywords     = {{algorithm; maximum agreement subtree; ordered tree; evolutionary tree; time complexity}},
  language     = {{eng}},
  number       = {{3}},
  pages        = {{233--248}},
  publisher    = {{Springer}},
  series       = {{Algorithmica}},
  title        = {{Polynomial-time algorithms for the ordered maximum agreement subtree problem}},
  url          = {{http://dx.doi.org/10.1007/s00453-007-0080-9}},
  doi          = {{10.1007/s00453-007-0080-9}},
  volume       = {{48}},
  year         = {{2007}},
}