Skip to main content

An optimal decomposition algorithm for tree edit distance

Publication ,  Journal Article
Demaine, ED; Mozes, S; Rossman, B; Weimann, O
Published in: ACM Transactions on Algorithms
December 1, 2009

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

ACM Transactions on Algorithms

DOI

EISSN

1549-6333

ISSN

1549-6325

Publication Date

December 1, 2009

Volume

6

Issue

1

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

APA
Chicago
ICMJE
MLA
NLM
Demaine, E. D., Mozes, S., Rossman, B., & Weimann, O. (2009). An optimal decomposition algorithm for tree edit distance. ACM Transactions on Algorithms, 6(1). https://doi.org/10.1145/1644015.1644017
Demaine, E. D., S. Mozes, B. Rossman, and O. Weimann. “An optimal decomposition algorithm for tree edit distance.” ACM Transactions on Algorithms 6, no. 1 (December 1, 2009). https://doi.org/10.1145/1644015.1644017.
Demaine ED, Mozes S, Rossman B, Weimann O. An optimal decomposition algorithm for tree edit distance. ACM Transactions on Algorithms. 2009 Dec 1;6(1).
Demaine, E. D., et al. “An optimal decomposition algorithm for tree edit distance.” ACM Transactions on Algorithms, vol. 6, no. 1, Dec. 2009. Scopus, doi:10.1145/1644015.1644017.
Demaine ED, Mozes S, Rossman B, Weimann O. An optimal decomposition algorithm for tree edit distance. ACM Transactions on Algorithms. 2009 Dec 1;6(1).

Published In

ACM Transactions on Algorithms

DOI

EISSN

1549-6333

ISSN

1549-6325

Publication Date

December 1, 2009

Volume

6

Issue

1

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