A survey on tree edit distance and related problems

DOI10.1016/j.tcs.2004.12.030zbMath1078.68152OpenAlexW1978478796MaRDI QIDQ557823

Philip Bille

Publication date: 30 June 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.12.030

zbMATH Keywords

tree edit distancetree inclusiontree alignmenttree matching problems

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Protein sequences, DNA sequences (92D20)

Related Items

Which XML schemas are streaming bounded repairable?, Succinct indices for path minimum, with applications, Dimension reduction in principal component analysis for trees, Tree inclusions in windows and slices, Quasifibrations of graphs to find symmetries and reconstruct biological networks, Algebraic dynamic programming on trees, Generalized LCS, Measuring the Distance Between Merge Trees, A relation between edit distance for ordered trees and edit distance for Euler strings, Approximating tree edit distance through string edit distance, Tree structure for contractible regions in \(\mathbb R^{3}\), Supervised classification and mathematical optimization, A metric normalization of tree edit distance, Tai mapping hierarchy for rooted labeled trees through common subforest, Unnamed Item, An Edit Distance Between Graph Correspondences, Fast similarity search for graphs by edit distance, Simulation relations for pattern matching in directed graphs, On the Parameterized Complexity of Associative and Commutative Unification, A survey on tree matching and XML retrieval, Characterization of random walks on space of unordered trees using efficient metric simulation, Exact algorithms for computing the tree edit distance between unordered trees, A metric for rooted trees with unlabeled vertices based on nested parentheses, 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, Unnamed Item, An expressive dissimilarity measure for relational clustering using neighbourhood trees, Good edit similarity learning by loss minimization, A theory of subtree matching and tree kernels based on the edit distance concept, Faster bit-parallel algorithms for unordered pseudo-tree matching and tree homeomorphism, Efficient exponential-time algorithms for edit distance between unordered trees, The graph matching problem, Space efficient algorithms for ordered tree comparison, Learning probabilistic models of tree edit distance, New dissimilarity measure for recognizing noisy subsequence trees, A framework for succinct labeled ordinal trees over large alphabets, Hierarchies and Ranks for Persistence Pairs, Improved MAX SNP-Hard Results for Finding an Edit Distance between Unordered Trees, Approximate XML structure validation based on document-grammar tree similarity, Algorithms for finding a most similar subforest, Improved approximation of the largest common subtree of two unordered trees of bounded height, An improved algorithm for tree edit distance with applications for RNA secondary structure comparison, A survey of graph edit distance, Unnamed Item, Comparing trees via crossing minimization, Unnamed Item, Normalization of edit sequences for text synchronization, On the parameterized complexity of associative and commutative unification, Fast algorithms for computing tree LCS, Dynamic path queries in linear space, Predicting the fault-proneness of class hierarchy in object-oriented software using a layered kernel, FPT-Algorithms for Computing Gromov-Hausdorff and Interleaving Distances Between Trees, New and improved algorithms for unordered tree inclusion, Approximating Tree Edit Distance through String Edit Distance for Binary Tree Codes, A new matching algorithm between trees of shapes and its application to brain tumor segmentation, Stability of the tree of shapes to additive noise, A Multi-labeled Tree Edit Distance for Comparing "Clonal Trees" of Tumor Progression., Reconstructing trees from traces, Local versus global distances for zigzag and multi-parameter persistence modules, A generalized Weisfeiler-Lehman graph kernel, Recursive tree grammar autoencoders, Covering tree with stars

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Alignment of trees -- an alternative to tree edit
• On the editing distance between unordered labeled trees
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• The tree-to-tree editing problem
• Some MAX SNP-hard results concerning unordered labeled trees
• Finding largest subtrees and smallest supertrees
• A constrained edit distance between unordered labeled trees
• New Algorithm for Ordered Tree-to-Tree Correction Problem
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
• A Tree-Matching Algorithm Based on Node Splitting and Merging
• Fast Algorithms for Finding Nearest Common Ancestors
• Finding approximate patterns in strings
• A Tree-to-Tree Distance and Its Application to Cluster Analysis
• Pattern Matching in Trees
• Bounds on the Complexity of the Longest Common Subsequence Problem
• The Tree-to-Tree Correction Problem
• Fast parallel and serial approximate string matching
• Algorithms on Strings, Trees and Sequences
• Approximate Tree Matching in the Presence of Variable Length Don′t Cares
• Nonlinear pattern matching in trees
• More Efficient Algorithm for Ordered Tree Inclusion
• The String-to-String Correction Problem
• Ordered and Unordered Tree Inclusion
• FINDING SMALLEST SUPERTREES UNDER MINOR CONTAINMENT
• Fast algorithms for the unit cost editing distance between trees