A metric for rooted trees with unlabeled vertices based on nested parentheses |
| |
| Authors: | Chan-Shuo Wu Guan-Shieng Huang |
| |
| Affiliation: | Department of Computer Science and Information Engineering, National Chi Nan University, Taiwan |
| |
| Abstract: | In this paper, we propose a new metric for rooted trees with unlabeled vertices based on alignments of nested parenthesis strings. We prove that the time complexity for computing this metric is NP-hard and present a 1.5-approximation algorithm for it. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
