@article{d8b25e7f53314ebba6e71c6ec1f7ce9d,
title = "On the editing distance between unordered labeled trees",
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.",
keywords = "Computational complexity, unordered trees",
author = "Kaizhong Zhang and Rick Statman and Dennis Shasha",
note = "Funding Information: Correspondence to: K. Zhang, Department of Computer Science, Universitv of Western Ontario. London, Ontario. Canada N6A 5B7. Email: kzhang@csd.uwo.ca. i Research supported by the National Sciences and En-gmeering Research Council of Canada grants OGP0046373 and the U.S. National Science Foundation under grant IRI-89-01699 and CCR-9103953 and by the U.S. Office of Naval Research under grants N00014-90-J-1110 and N00014-91-J-1472. * * Email: shasha@ca.nyu.edu. Copyright: Copyright 2014 Elsevier B.V., All rights reserved.",
year = "1992",
month = may,
day = "25",
doi = "10.1016/0020-0190(92)90136-J",
language = "English (US)",
volume = "42",
pages = "133--139",
journal = "Information Processing Letters",
issn = "0020-0190",
publisher = "Elsevier",
number = "3",
}