The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Polynomial-time algorithms for the ordered maximum agreement subtree problem

På svenska

Author

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{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.

Department/s

  • Computer Science

Publishing year

2004

Language

English

Pages

220-229

Publication/Series

Combinatorial pattern matching / Lecture notes in computer science

Volume

3109

Document type

Conference paper

Publisher

Springer

Topic

  • Computer Science

Conference name

15th Annual Symposium, CPM 2004

Conference date

2004-07-05 - 2004-07-07

Conference place

Istanbul, Turkey

Status

Published

Project

  • VR 2002-4049

ISBN/ISSN/Other

  • ISSN: 1611-3349
  • ISSN: 0302-9743
  • ISBN: 3-540-22341-X