Algorithmic aspects of tree amalgamation

被引：24

作者：

Böcker, S

Bryant, D

Dress, AWM

Steel, MA

机构：

[1] Univ Bielefeld, FSP Mathematisierung, GK Strukturbildungsprozesse, D-33501 Bielefeld, Germany

[2] LIRMM, F-34392 Montpellier 5, France

[3] Univ Canterbury, Biomath Res Ctr, Christchurch 1, New Zealand

来源：

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC | 2000年 / 37卷 / 02期

基金：

加拿大自然科学与工程研究理事会;

关键词：

trees; algorithms; dyadic closure; tree amalgamation;

D O I：

10.1006/jagm.2000.1116

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The amalgamation of leaf-labeled trees into a single (super)tree that "displays" each of the input trees is an important problem in classification. We discuss various approaches to this problem and show that a simple and well-known polynomial-time algorithm can be used to solve this problem whenever the input set of trees contains a minimum size subset that uniquely determines the supertree. Our results exploit a recently established combinatorial property concerning the structure of such collections of trees. (C) 2000 Academic Press.

引用

页码：522 / 537

页数：16

共 18 条

[1] INFERRING A TREE FROM LOWEST COMMON ANCESTORS WITH AN APPLICATION TO THE OPTIMIZATION OF RELATIONAL EXPRESSIONS [J].