ON THE AGREEMENT OF MANY TREES

被引：67

作者：

FARACH, M

PRZYTYCKA, TM

THORUP, M

机构：

[1] ODENSE UNIV,DEPT MATH & COMP SCI,DK-5230 ODENSE M,DENMARK

[2] UNIV COPENHAGEN,DEPT COMP SCI,DK-2100 COPENHAGEN O,DENMARK

来源：

INFORMATION PROCESSING LETTERS | 1995年 / 55卷 / 06期

关键词：

ANALYSIS; DESIGN OF ALGORITHMS; COMPUTATIONAL BIOLOGY; PHYLOGENETIC TREES;

D O I：

10.1016/0020-0190(95)00110-X

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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(3) + n(d)).

引用

页码：297 / 301

页数：5

共 9 条

[1]

AMIR A, 1995, UNPUB MAXIMUM AGREEM

[2]

AMIR A, 1994, 35TH P IEEE ANN S CO, P758

[3]

BARTHELENY JP, 1991, TREES PROXIMITY REPR

[4]

FARACH M, 1994, 5TH P ANN ACM SIAM S, P481

[5]

FARACH M, 1994, 35 ANN S FDN COMP SC, P770

[6]

FARACH M, 1995, 3RD P ANN EUR S ALG

[7] OBTAINING COMMON PRUNED TREES [J].

FINDEN, CR ;

GORDON, AD .

JOURNAL OF CLASSIFICATION, 1985, 2 (2-3) :255-276

[8]

KUBICKA E, 1994, J CLASSIFICATION

[9] KAIKOURA TREE THEOREMS - COMPUTING THE MAXIMUM AGREEMENT SUBTREE [J].

STEEL, M ;

WARNOW, T .

INFORMATION PROCESSING LETTERS, 1993, 48 (02) :77-82

← 1 →