An optimal decomposition algorithm for tree edit distance
The edit distance between two ordered rooted 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 article, we present a worst-case O(n 3)-time algorithm for the problem when the two trees have size n, improving the previous best O(n3 log n)-time algorithm. Our result requires a novel adaptive strategy for deciding how a dynamic program divides into subproblems, together with a deeper understanding of the previous algorithms for the problem. We prove the optimality of our algorithm among the family of decomposition strategy algorithmswhich also includes the previous fastest algorithmsby tightening the known lower bound of ω(n2 log2 n) to ω(n3), matching our algorithm's running time. Furthermore, we obtain matching upper and lower bounds for decomposition strategy algorithms of Θ(nm2 (1 + log n/m)) when the two trees have sizes m and n and m < n. © 2009 ACM.
Duke Scholars
Altmetric Attention Stats
Dimensions Citation Stats
Published In
DOI
EISSN
ISSN
Publication Date
Volume
Issue
Related Subject Headings
- Computation Theory & Mathematics
- 4901 Applied mathematics
- 4613 Theory of computation
- 4605 Data management and data science
- 0802 Computation Theory and Mathematics
- 0103 Numerical and Computational Mathematics
Citation
Published In
DOI
EISSN
ISSN
Publication Date
Volume
Issue
Related Subject Headings
- Computation Theory & Mathematics
- 4901 Applied mathematics
- 4613 Theory of computation
- 4605 Data management and data science
- 0802 Computation Theory and Mathematics
- 0103 Numerical and Computational Mathematics