An optimal decomposition algorithm for tree edit distance

DOI10.1145/1644015.1644017MaRDI QIDQ2930275zbMATH OpenOpenAlexWikidataFDO

Authors Erik D. Demaine, Shay Mozes, Benjamin Rossman, Oren Weimann

Publication date 18 November 2014

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0604037

zbMATH Keywords

dynamic programmingedit distanceordered treestree edit distancedecomposition strategy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Nonnumerical algorithms (68W05)

Abstract: The {em edit distance} between two ordered trees with vertex labels is the minimum cost of transforming one tree into the other by a sequence of elementary operations consisting of deleting and relabeling existing nodes, as well as inserting new nodes. In this paper, we present a worst-case $O(n^3)$-time algorithm for this problem, improving the previous best $O(n^{3}logn)$-time algorithm~cite{Klein}. Our result requires a novel adaptive strategy for deciding how a dynamic program divides into subproblems (which is interesting in its own right), together with a deeper understanding of the previous algorithms for the problem. We also prove the optimality of our algorithm among the family of emph{decomposition strategy} algorithms--which also includes the previous fastest algorithms--by tightening the known lower bound of $Omega(n^{2}lo{g}^{2}n)$~cite{Touzet} to $Omega(n^3)$, matching our algorithm's running time. Furthermore, we obtain matching upper and lower bounds of $Theta(n{m}^2(1+logfracnm))$ when the two trees have different sizes $m$ and~$n$, where $m<n$.

Recommendations

• An Optimal Decomposition Algorithm for Tree Edit Distance
• Decomposition algorithms for the tree edit distance problem
• Efficient computation of the tree edit distance
• Edit distance between unrooted trees in cubic time
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems

Cited in

(29)

• An Optimal Decomposition Algorithm for Tree Edit Distance
• Algorithms for finding a most similar subforest
• Improved MAX SNP-hard results for finding an edit distance between unordered trees
• scientific article; zbMATH DE number 7561381 (Why is no real title available?)
• Edit distance between unrooted trees in cubic time
• Efficient computation of the tree edit distance
• Fast algorithms for the unit cost editing distance between trees
• Analysis of tree edit distance algorithms
• Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (Unless APSP Can)
• An improved algorithm for tree edit distance with applications for RNA secondary structure comparison
• Efficient chaining of seeds in ordered trees
• Decomposition algorithms for the tree edit distance problem
• Faster algorithms for bounded tree edit distance
• New algorithm for ordered tree-to-tree correction problem
• On the complexity of finding a largest common subtree of bounded degree
• Tree edit distance cannot be computed in strongly subcubic time (unless APSP can)
• New and improved algorithms for unordered tree inclusion
• Mining approximate patterns with frequent locally optimal occurrences
• Modeling dynamic programming problems over sequences and trees with inverse coupled rewrite systems
• Efficient exponential-time algorithms for edit distance between unordered trees
• Approximation and special cases of common subtrees and editing distance
• Tai mapping hierarchy for rooted labeled trees through common subforest
• Efficient Chaining of Seeds in Ordered Trees
• Weighted edit distance computation: strings, trees, and Dyck
• Inexact tree pattern matching with 1-degree edit distance using finite automata
• On the hardness of computing the edit distance of shallow trees
• Alignment distance of regular tree languages
• Alignment distance of regular tree languages
• An edit distance between quotiented trees

This page was built for publication: An optimal decomposition algorithm for tree edit distance

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