Authors
Kaizhong Zhang, Rick Statman, Dennis Shasha
Publication date
1992/5/25
Journal
Information processing letters
Volume
42
Issue
3
Pages
133-139
Publisher
Elsevier
Description
This paper considers the problem of computing the editing distance between unordered, labeled trees. We give efficient polynomial-time algorithms for the case when one tree is a string or has a bounded number of leaves. By contrast, we show that the problem is NP-complete even for binary trees having a label alphabet of size two.
Total citations
Scholar articles
K Zhang, R Statman, D Shasha - Information processing letters, 1992