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

被引：58

作者：

Cole, R

Colton, MF

Hariharan, R

Przytycka, T

Thorup, M

机构：

[1] NYU, Courant Inst Math Sci, New York, NY 10012 USA

[2] DIMACS, Piscataway, NJ 08855 USA

[3] Rutgers State Univ, Piscataway, NJ 08855 USA

[4] Indian Inst Sci, Bangalore 560012, Karnataka, India

[5] Max Planck Inst Informat, Saarbrucken, Germany

[6] Johns Hopkins Univ, Sch Med, Baltimore, MD 21205 USA

[7] AT&T Labs Res, Shannon Lab, Florham Park, NJ 07932 USA

[8] Univ Copenhagen, DK-1168 Copenhagen, Denmark

[9] MIT, Cambridge, MA 02139 USA

来源：

SIAM JOURNAL ON COMPUTING | 2000年 / 30卷 / 05期

关键词：

algorithms; agreement subtree;

D O I：

10.1137/S0097539796313477

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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

引用

页码：1385 / 1404

页数：20

共 14 条

[1] Maximum agreement subtree in a set of evolutionary trees: Metrics and efficient algorithms [J].