An O(n log n) algorithm for the maximum agreement subtree problem for binary trees

Richard Cole, Martin Farach-Colton, Ramesh Hariharan, Teresa Przytycka, Mikkel Thorup

Research output: Contribution to journalArticlepeer-review

Abstract

The maximum agreement subtree problem is the following. Given two rooted trees whose leaves are drawn from the same set of items (e.g., species), find the largest subset of these items so that the portions of the two trees restricted to these items are isomorphic. We consider the case which occurs frequently in practice, i.e., the case when the trees are binary, and give an O(n log n) time algorithm for this problem.

Original languageEnglish (US)
Pages (from-to)1385-1404
Number of pages20
JournalSIAM Journal on Computing
Volume30
Issue number5
DOIs
StatePublished - 2000

Keywords

  • Agreement subtree
  • Algorithms

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'An O(n log n) algorithm for the maximum agreement subtree problem for binary trees'. Together they form a unique fingerprint.

Cite this