Improved approximation of the largest common subtree of two unordered trees of bounded height |
| |
| Authors: | Tatsuya Akutsu Daiji Fukagawa Atsuhiro Takasu |
| |
| Affiliation: | a Bioinformatics Center, Institute for Chemical Research, Kyoto University, Kyoto 611-0011, Japan
b National Institute of Informatics, Tokyo 101-8430, Japan |
| |
| Abstract: | 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. |
| |
| Keywords: | Approximation algorithms Edit distance Unordered trees Common subtrees |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
