Advanced

Polynomial-time algorithms for the ordered maximum agreement subtree problem

Dessmark, Anders LU ; Jansson, Jesper LU ; Lingas, Andrzej LU and Lundell, Eva-Marta LU (2004) 15th Annual Symposium, CPM 2004 In Combinatorial pattern matching / Lecture notes in computer science 3109. p.220-229
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{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.
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
Combinatorial pattern matching / Lecture notes in computer science
volume
3109
pages
220 - 229
publisher
Springer
conference name
15th Annual Symposium, CPM 2004
external identifiers
  • wos:000222627600016
  • scopus:34547253932
ISSN
0302-9743
1611-3349
ISBN
3-540-22341-X
DOI
10.1007/s00453-007-0080-9
project
VR 2002-4049
language
English
LU publication?
yes
id
6d5801f3-0766-43cc-96b0-b4b45e3cede6 (old id 272539)
date added to LUP
2007-10-23 13:36:33
date last changed
2017-01-01 05:09:45
@inproceedings{6d5801f3-0766-43cc-96b0-b4b45e3cede6,
  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{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.},
  author       = {Dessmark, Anders and Jansson, Jesper and Lingas, Andrzej and Lundell, Eva-Marta},
  booktitle    = {Combinatorial pattern matching / Lecture notes in computer science},
  isbn         = {3-540-22341-X},
  issn         = {0302-9743},
  language     = {eng},
  pages        = {220--229},
  publisher    = {Springer},
  title        = {Polynomial-time algorithms for the ordered maximum agreement subtree problem},
  url          = {http://dx.doi.org/10.1007/s00453-007-0080-9},
  volume       = {3109},
  year         = {2004},
}