On the editing distance between unordered labeled trees

DOI10.1016/0020-0190(92)90136-JMaRDI QIDQ1198043zbMATH OpenFDO

Authors Dennis Shasha, Kaizhong Zhang, Richard Statman

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)

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

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On the editing distance between unordered labeled trees
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
• The String-to-String Correction Problem
• The Tree-to-Tree Correction Problem

Cited in

(39)

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

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)