On the editing distance between unordered labeled trees

Kaizhong Zhang, Rick Statman, Dennis Shasha

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)133-139
Number of pages7
JournalInformation Processing Letters
Volume42
Issue number3
DOIs
StatePublished - May 25 1992

Keywords

  • Computational complexity
  • unordered trees

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Fingerprint Dive into the research topics of 'On the editing distance between unordered labeled trees'. Together they form a unique fingerprint.

Cite this