Improved approximation of the largest common subtree of two unordered trees of bounded height

被引：6

作者：

Akutsu, Tatsuya ^{[1
]}

Fukagawa, Daiji ^{[2
]}

Takasu, Atsuhiro ^{[2
]}

机构：

[1] Kyoto Univ, Inst Chem Res, Bioinformat Ctr, Kyoto 6110011, Japan

[2] Res Org Informat & Syst, Natl Inst Informat, Tokyo 1018430, Japan

来源：

INFORMATION PROCESSING LETTERS | 2008年 / 109卷 / 02期

关键词：

Approximation algorithms; Edit distance; Unordered trees; Common subtrees;

D O I：

10.1016/j.ipl.2008.09.025

中图分类号：

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

学科分类号：

0812 ;

摘要：

We present a polynomial time 1.5h-approximation algorithm for the problem of finding the largest common subtree between two rooted, labeled, and unordered trees of height at most h, where a tree S is called a subtree of a tree T if S is obtained from T by deletion of some nodes in T. This result improves the previous 2h-approximation algorithm. (C) 2008 Elsevier B.V. All rights reserved.

引用

页码：165 / 170

页数：6

共 8 条

[1] A survey on tree edit distance and related problems [J].