Fast algorithms for the unit cost editing distance between trees

DOI10.1016/0196-6774(90)90011-3MaRDI QIDQ5750416zbMATH OpenOpenAlexFDO

Authors Dennis Shasha, Kaizhong Zhang

Publication date 1990

Published in Journal of Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1016/0196-6774(90)90011-3

zbMATH Keywords

distance between treesdynamic programmingparallel algorithms

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Dynamic programming (90C39)

Recommendations

• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
• An Optimal Decomposition Algorithm for Tree Edit Distance
• An optimal decomposition algorithm for tree edit distance
• Constrained tree editing
• Analysis of tree edit distance algorithms

Cited in

(24)

• Algorithms for approximate graph matching
• Efficient exponential-time algorithms for edit distance between unordered trees
• An algebraic view of the relation between largest common subtrees and smallest common supertrees
• Decomposition algorithms for the tree edit distance problem
• New dissimilarity measure for recognizing noisy subsequence trees
• scientific article; zbMATH DE number 2185644 (Why is no real title available?)
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
• Analysis of tree edit distance algorithms
• Numerical similarity and dissimilarity measures between two trees
• scientific article; zbMATH DE number 2043356 (Why is no real title available?)
• Edit distance between unrooted trees in cubic time
• Efficient computation of the tree edit distance
• A multi-labeled tree edit distance for comparing ``Clonal trees of tumor progression
• Theoretical Computer Science
• FAST ALGORITHMS FOR COMPARISON OF SIMILAR UNORDERED TREES
• A survey on tree edit distance and related problems
• Scale Space and PDE Methods in Computer Vision
• Membrane Computing
• On the hardness of computing the edit distance of shallow trees
• Approximation and special cases of common subtrees and editing distance
• A parallel tree difference algorithm
• Faster algorithms for bounded tree edit distance
• A relation between edit distance for ordered trees and edit distance for Euler strings
• Faster algorithms for guided tree edit distance

This page was built for publication: Fast algorithms for the unit cost editing distance between trees

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