Abstract
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.
Original language | English (US) |
---|---|
Pages (from-to) | 133-139 |
Number of pages | 7 |
Journal | Information Processing Letters |
Volume | 42 |
Issue number | 3 |
DOIs | |
State | Published - May 25 1992 |
Keywords
- Computational complexity
- unordered trees
ASJC Scopus subject areas
- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications