Polynomial-time algorithms for the ordered maximum agreement subtree problem

Anders Dessmark, Jesper Andreas Jansson, Andrzej Lingas, Eva Marta Lundell

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

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-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.
Original languageEnglish
Title of host publicationCombinatorial Pattern Matching, 15th Annual Symposium, CPM 2004, Istanbul, Turkey, July 2004 Proceedings
EditorsSuleyman Cenk Sahinalp , S. Muthukrishnan , Ugur Dogrusoz
Pages220-229
Number of pages10
DOIs
Publication statusPublished - 2004
Externally publishedYes
Event15th Annual Symposium on Combinatorial Pattern Matching, CPM 2004 - Istanbul, Turkey
Duration: 5 Jul 20047 Jul 2004

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
VolumeLNCS 3109
ISSN (Electronic)0302-9743

Conference

Conference15th Annual Symposium on Combinatorial Pattern Matching, CPM 2004
CountryTurkey
CityIstanbul
Period5/07/047/07/04

Keywords

  • Algorithm
  • Evolutionary tree
  • Maximum agreement subtree
  • Ordered tree
  • Time complexity

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Cite this