Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
From MaRDI portal
DOI10.1137/0218082zbMATH Open0692.68047OpenAlexW1976373002MaRDI QIDQ3034830FDOQ3034830
Authors: Kaizhong Zhang, 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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39) Data structures (68P05)
Cited In (only showing first 100 items - show all)
- Identifying consensus of trees through alignment
- Forest alignment with affine gaps and anchors, applied in RNA structure comparison
- A survey on tree matching and XML retrieval
- An Optimal Decomposition Algorithm for Tree Edit Distance
- An overview on XML similarity: background, current trends and future directions
- Finding approximate patterns in undirected acyclic graphs
- Algorithms for finding a most similar subforest
- Approximation of RNA multiple structural alignment
- Graph embedding using tree edit-union
- Title not available (Why is that?)
- Supervised classification and mathematical optimization
- Finding similar consensus between trees: An algorithm and a distance hierarchy
- On the similarity metric and the distance metric
- Comparing similar ordered trees in linear-time
- A survey of graph edit distance
- 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
- Algorithms and Computation
- Image categorization: Graph edit distance \(+\) edge direction histogram
- An efficient algorithm for some tree matching problems
- A relation between edit distance for ordered trees and edit distance for Euler strings
- Computing similarity between RNA structures
- Fast algorithms for the unit cost editing distance between trees
- Comparing trees via crossing minimization
- Tree edit distance with gaps
- Computing approximate tree edit distance using relaxation labeling
- Fast algorithms for computing tree LCS
- Dissimilarity between two skeletal trees in a context
- A constrained edit distance algorithm between semi-ordered trees
- Sublinear DTD validity
- Efficient chaining of seeds in ordered trees
- Tree edit distance and maximum agreement subtree
- An algebraic view of the relation between largest common subtrees and smallest common supertrees
- Approximating Tree Edit Distance through String Edit Distance for Binary Tree Codes
- A string matching based algorithm for performance evaluation of mathematical expression recognition
- Decomposition algorithms for the tree edit distance problem
- FAST ALGORITHMS FOR COMPARISON OF SIMILAR UNORDERED TREES
- New algorithm for ordered tree-to-tree correction problem
- A constrained edit distance between unordered labeled trees
- Algorithms for approximate graph matching
- Kernelization and parameterized algorithms for covering a tree by a set of stars or paths
- Combinatorial Pattern Matching
- Forest Alignment with Affine Gaps and Anchors
- Some MAX SNP-hard results concerning unordered labeled trees
- A new algorithm for aligning nested arc-annotated sequences under arbitrary weight schemes
- A theory of subtree matching and tree kernels based on the edit distance concept
- Title not available (Why is that?)
- On the editing distance between unordered labeled trees
- Alignment of trees -- an alternative to tree edit
- Identifying approximately common substructures in trees based on a restricted edit distance
- Local similarity between quotiented ordered trees
- Approximation and special cases of common subtrees and editing distance
- A metric normalization of tree edit distance
- Generalized LCS
- Space efficient algorithms for ordered tree comparison
- Learning probabilistic models of tree edit distance
- On the complexity of comparing evolutionary trees
- Approximate joins for XML at label level
- An edit distance between quotiented trees
- RNA secondary structure comparison: Exact analysis of the Zhang-Shasha tree edit algorithm.
- An optimal decomposition algorithm for tree edit distance
- Approximate XML structure validation based on document-grammar tree similarity
- Improving strategic decisions in sequential games by exploiting positional similarity
- Weighted edit distance computation: strings, trees, and Dyck
- On the hardness of computing the edit distance of shallow trees
- Comparative assessment of alignment algorithms for NGS data: features, considerations, implementations, and future
- Algorithms for local similarity between forests
- Recursive tree grammar autoencoders
- Approximating tree edit distance through string edit distance
- Improved MAX SNP-hard results for finding an edit distance between unordered trees
- Approximation of trees by self-nested trees
- Title not available (Why is that?)
- Optimal mappings with minimum number of connected components in tree-to-tree comparison problems
- Segmental mapping and distance for rooted labeled ordered trees
- Normalization of edit sequences for text synchronization
- Approximate matching for two families of trees
- Title not available (Why is that?)
- The Bourque distances for mutation trees of cancers
- Efficient computation of the tree edit distance
- Development and analysis of a sentence semantics representation model
- Finding smallest supertrees
- Extending E prover with similarity based clause selection strategies
- Resequencing a set of strings based on a target string
- A new algorithm for computing similarity between RNA structures
- An improved algorithm for tree edit distance with applications for RNA secondary structure comparison
- A multi-labeled tree edit distance for comparing ``Clonal trees of tumor progression
- Caterpillar alignment distance for rooted labeled caterpillars: distance based on alignments required to be caterpillars
- Fast Algorithms for Computing Tree LCS
- Approximation and parameterized algorithms for common subtrees and edit distance between unordered trees
- A new constrained edit distance between quotiented ordered trees
- Membrane Computing
- Tree edit distance cannot be computed in strongly subcubic time (unless APSP can)
- Computer Vision - ECCV 2004
- Segmental mapping and distance for rooted labeled ordered trees
- Numerical similarity and dissimilarity measures between two trees
- Constrained tree editing
- An Improved Algorithm for Tree Edit Distance Incorporating Structural Linearity
- Efficient exponential-time algorithms for edit distance between unordered trees
This page was built for publication: Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3034830)
