Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
From MaRDI portal
Publication:3034830
DOI10.1137/0218082zbMath0692.68047OpenAlexW1976373002MaRDI QIDQ3034830
Zhang, Kaizhong, Dennis Shasha
Publication date: 1989
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0218082
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39) Data structures (68P05)
Related Items
Constrained tree editing ⋮ Development and analysis of a sentence semantics representation model ⋮ A VLSI algorithm for calculating the tree to tree distance ⋮ Quasifibrations of graphs to find symmetries and reconstruct biological networks ⋮ Algebraic dynamic programming on trees ⋮ Generalized LCS ⋮ A relation between edit distance for ordered trees and edit distance for Euler strings ⋮ Approximating tree edit distance through string edit distance ⋮ Algorithms for approximate graph matching ⋮ Supervised classification and mathematical optimization ⋮ A constrained edit distance between unordered labeled trees ⋮ A metric normalization of tree edit distance ⋮ TRACTABLE AND INTRACTABLE VARIATIONS OF UNORDERED TREE EDIT DISTANCE ⋮ Graph embedding using tree edit-union ⋮ Forest alignment with affine gaps and anchors, applied in RNA structure comparison ⋮ A survey on tree matching and XML retrieval ⋮ On the hardness of computing the edit distance of shallow trees ⋮ Fast Algorithms for Computing Tree LCS ⋮ Kernelization and parameterized algorithms for covering a tree by a set of stars or paths ⋮ A new algorithm for aligning nested arc-annotated sequences under arbitrary weight schemes ⋮ Good edit similarity learning by loss minimization ⋮ A theory of subtree matching and tree kernels based on the edit distance concept ⋮ Algorithms for local similarity between forests ⋮ Efficient chaining of seeds in ordered trees ⋮ An overview on XML similarity: background, current trends and future directions ⋮ RNA secondary structure comparison: Exact analysis of the Zhang-Shasha tree edit algorithm. ⋮ Local similarity between quotiented ordered trees ⋮ Comparing similar ordered trees in linear-time ⋮ Approximation of RNA multiple structural alignment ⋮ Space efficient algorithms for ordered tree comparison ⋮ Learning probabilistic models of tree edit distance ⋮ Identifying approximately common substructures in trees based on a restricted edit distance ⋮ New dissimilarity measure for recognizing noisy subsequence trees ⋮ Image categorization: Graph edit distance \(+\) edge direction histogram ⋮ An efficient algorithm for some tree matching problems ⋮ Efficient Chaining of Seeds in Ordered Trees ⋮ Comparative Assessment of Alignment Algorithms for NGS Data: Features, Considerations, Implementations, and Future ⋮ Alignment of trees -- an alternative to tree edit ⋮ Approximate joins for XML at label level ⋮ Forest Alignment with Affine Gaps and Anchors ⋮ Improved MAX SNP-Hard Results for Finding an Edit Distance between Unordered Trees ⋮ On the editing distance between unordered labeled trees ⋮ Finding similar consensus between trees: An algorithm and a distance hierarchy ⋮ Approximate XML structure validation based on document-grammar tree similarity ⋮ Algorithms for finding a most similar subforest ⋮ Identifying consensus of trees through alignment ⋮ Average complexity of the Jiang-Wang-Zhang pairwise tree alignment algorithm and of an RNA secondary structure alignment algorithm ⋮ Finding common structured patterns in linear graphs ⋮ Faster algorithms for guided tree edit distance ⋮ A survey on tree edit distance and related problems ⋮ An improved algorithm for tree edit distance with applications for RNA secondary structure comparison ⋮ A survey of graph edit distance ⋮ Comparing trees via crossing minimization ⋮ A new algorithm for computing similarity between RNA structures ⋮ Normalization of edit sequences for text synchronization ⋮ An algebraic view of the relation between largest common subtrees and smallest common supertrees ⋮ Finding approximate patterns in undirected acyclic graphs ⋮ On the complexity of comparing evolutionary trees ⋮ Sublinear DTD Validity ⋮ Fast algorithms for computing tree LCS ⋮ Dissimilarity between two skeletal trees in a context ⋮ A constrained edit distance algorithm between semi-ordered trees ⋮ Predicting the fault-proneness of class hierarchy in object-oriented software using a layered kernel ⋮ A new constrained edit distance between quotiented ordered trees ⋮ A string matching based algorithm for performance evaluation of mathematical expression recognition ⋮ Extending E Prover with Similarity Based Clause Selection Strategies ⋮ On the similarity metric and the distance metric ⋮ Approximating Tree Edit Distance through String Edit Distance for Binary Tree Codes ⋮ A Multi-labeled Tree Edit Distance for Comparing "Clonal Trees" of Tumor Progression. ⋮ FAST ALGORITHMS FOR COMPARISON OF SIMILAR UNORDERED TREES ⋮ Reconstructing trees from traces ⋮ Decomposition algorithms for the tree edit distance problem ⋮ Edit distance between unlabeled ordered trees ⋮ Tree edit distance with gaps ⋮ Recursive tree grammar autoencoders ⋮ Some MAX SNP-hard results concerning unordered labeled trees ⋮ Computing similarity between RNA structures ⋮ Resequencing a set of strings based on a target string
