On the editing distance between unordered labeled trees

DOI10.1016/0020-0190(92)90136-JzbMath0780.68070MaRDI QIDQ1198043

Dennis Shasha, Richard Statman, Zhang, Kaizhong

Publication date: 16 January 1993

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

NP-completepolynomial-time algorithmsunordered treesediting distance between unordered, labeled trees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05)

Related Items

Comparing large graphs efficiently by margins of feature vectors, Algorithms for approximate graph matching, A similarity measure for graphs with low computational complexity, A constrained edit distance between unordered labeled trees, TRACTABLE AND INTRACTABLE VARIATIONS OF UNORDERED TREE EDIT DISTANCE, Graph embedding using tree edit-union, Treelet kernel incorporating cyclic, stereo and inter pattern information in chemoinformatics, Characterization of random walks on space of unordered trees using efficient metric simulation, Exact algorithms for computing the tree edit distance between unordered trees, Automated methods for the comparison of natural languages, Inexact tree pattern matching with 1-degree edit distance using finite automata, Anti Tai mapping for unordered labeled trees, Efficient exponential-time algorithms for edit distance between unordered trees, Tree edit distance and maximum agreement subtree, Isomorphism testing via polynomial-time graph extensions, New dissimilarity measure for recognizing noisy subsequence trees, Alignment of trees -- an alternative to tree edit, Improved MAX SNP-Hard Results for Finding an Edit Distance between Unordered Trees, On the editing distance between unordered labeled trees, Improved approximation of the largest common subtree of two unordered trees of bounded height, A survey on tree edit distance and related problems, Unnamed Item, New and improved algorithms for unordered tree inclusion, Alignment distance of regular tree languages, Alignment distance of regular tree languages, Tree edit distance with gaps, On the complexity of finding a largest common subtree of bounded degree, Some MAX SNP-hard results concerning unordered labeled trees, Covering tree with stars

Cites Work

• On the editing distance between unordered labeled trees
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
• The Tree-to-Tree Correction Problem
• The String-to-String Correction Problem
• Unnamed Item