On the agreement of many trees

Martin Farach; Teresa M. Przytycka; Mikkel Thorup

doi:10.1016/0020-0190(95)00110-X

On the agreement of many trees

Martin Farach, Teresa M. Przytycka, Mikkel Thorup

Research output: Contribution to journal › Article › peer-review

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(kn³ + n^d).

Original language	English (US)
Pages (from-to)	297-301
Number of pages	5
Journal	Information Processing Letters
Volume	55
Issue number	6
DOIs	https://doi.org/10.1016/0020-0190(95)00110-X
State	Published - Sep 29 1995

Keywords

Analysis
Computational biology
Design of algorithms
Phylogentic trees

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Access to Document

10.1016/0020-0190(95)00110-X

Cite this

@article{bddc53e3c0f94bd6ba099a0afc882d06,

title = "On the agreement of many trees",

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).",

keywords = "Analysis, Computational biology, Design of algorithms, Phylogentic trees",

author = "Martin Farach and Przytycka, {Teresa M.} and Mikkel Thorup",

year = "1995",

month = sep,

day = "29",

doi = "10.1016/0020-0190(95)00110-X",

language = "English (US)",

volume = "55",

pages = "297--301",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "6",

}

TY - JOUR

T1 - On the agreement of many trees

AU - Farach, Martin

AU - Przytycka, Teresa M.

AU - Thorup, Mikkel

PY - 1995/9/29

Y1 - 1995/9/29

N2 - 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).

AB - 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).

KW - Analysis

KW - Computational biology

KW - Design of algorithms

KW - Phylogentic trees

UR - http://www.scopus.com/inward/record.url?scp=0006643131&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0006643131&partnerID=8YFLogxK

U2 - 10.1016/0020-0190(95)00110-X

DO - 10.1016/0020-0190(95)00110-X

M3 - Article

AN - SCOPUS:0006643131

SN - 0020-0190

VL - 55

SP - 297

EP - 301

JO - Information Processing Letters

JF - Information Processing Letters

IS - 6

ER -

On the agreement of many trees

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this