On the editing distance between unordered labeled trees

DOI10.1016/0020-0190(92)90136-JzbMATH Open0780.68070MaRDI QIDQ1198043FDOQ1198043

Dennis Shasha, Richard Statman, Kaizhong Zhang

Publication date: 16 January 1993

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

Recommendations

• A constrained edit distance between unordered labeled trees
• A survey on tree edit distance and related problems
• scientific article; zbMATH DE number 1305084
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
• Exact algorithms for computing the tree edit distance between unordered trees

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)

Cites Work

• Title not available (Why is that?)
• The Tree-to-Tree Correction Problem
• The String-to-String Correction Problem
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
• On the editing distance between unordered labeled trees

Cited In (33)

• Improved MAX SNP-Hard Results for Finding an Edit Distance between Unordered Trees
• Graph embedding using tree edit-union
• A similarity measure for graphs with low computational complexity
• Title not available (Why is that?)
• Title not available (Why is that?)
• Improved approximation of the largest common subtree of two unordered trees of bounded height
• A survey on tree edit distance and related problems
• Comparing large graphs efficiently by margins of feature vectors
• Covering tree with stars
• Automated methods for the comparison of natural languages
• Tree edit distance with gaps
• ON THE EDITING DISTANCE BETWEEN UNDIRECTED ACYCLIC GRAPHS
• Characterization of random walks on space of unordered trees using efficient metric simulation
• Tree edit distance and maximum agreement subtree
• A constrained edit distance between unordered labeled trees
• On the complexity of finding a largest common subtree of bounded degree
• Algorithms for approximate graph matching
• Exact algorithms for computing the tree edit distance between unordered trees
• Anti Tai mapping for unordered labeled trees
• New and improved algorithms for unordered tree inclusion
• Some MAX SNP-hard results concerning unordered labeled trees
• Treelet kernel incorporating cyclic, stereo and inter pattern information in chemoinformatics
• On the editing distance between unordered labeled trees
• Alignment of trees -- an alternative to tree edit
• Approximation and special cases of common subtrees and editing distance
• Efficient exponential-time algorithms for edit distance between unordered trees
• New dissimilarity measure for recognizing noisy subsequence trees
• Inexact tree pattern matching with 1-degree edit distance using finite automata
• Tractable and intractable variations of unordered tree edit distance
• Title not available (Why is that?)
• Alignment distance of regular tree languages
• Alignment distance of regular tree languages
• Isomorphism testing via polynomial-time graph extensions

This page was built for publication: On the editing distance between unordered labeled trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1198043)