A metric for rooted trees with unlabeled vertices based on nested parentheses
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. (C) 2010 Elsevier B.V. All rights reserved.
nested parenthesis strings tree metric np-completeness approximation algorithm