Polynomial-time algorithms for the ordered maximum agreement subtree problem

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

Research output: Journal article publicationJournal articleAcademic researchpeer-review

3 Citations (Scopus)

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(kn3), O(n3mm{nk, n + log k-1 n}), O(kn3), and O((k + n)n3), respectively, where n is the number of leaf labels and k is the number of input trees.
Original languageEnglish
Pages (from-to)220-229
Number of pages10
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3109
Publication statusPublished - 1 Dec 2004
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this