On the agreement of many trees

Martin Farach, Teresa M. Przytycka, Mikkel Thorup

Research output: Contribution to journalArticlepeer-review

79 Scopus citations

Abstract

We consider the problem of computing the Maximum Agreement Subtree (MAST) of a set of rooted leaf labeled trees. We give an algorithm which computes the MAST of k trees on n leaves where some tree has maximum outdegree d in time O(kn3 + nd).

Original languageEnglish (US)
Pages (from-to)297-301
Number of pages5
JournalInformation Processing Letters
Volume55
Issue number6
DOIs
StatePublished - Sep 29 1995

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Keywords

  • Analysis
  • Computational biology
  • Design of algorithms
  • Phylogentic trees

Fingerprint Dive into the research topics of 'On the agreement of many trees'. Together they form a unique fingerprint.

Cite this