**Reference**:- Erik D. Demaine, Shay Mozes, Benjamin Rossman, and Oren Weimann, “An Optimal Decomposition Algorithm for Tree Edit Distance”, in
*Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP 2007)*, Wroclaw, Poland, July 9–13, 2007, pages 146–157. **Abstract**:-
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 paper, we present a worst-case*O*(n^{3})-time algorithm for this problem, improving the previous best*O*(*n*^{3}log*n*)-time algorithm [9]. 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*algorithms—which also includes the previous fastest algorithms—by tightening the known lower bound of Ω(*n*^{2}log^{2}*n*) [6] to Ω(*n*^{3}), matching our algorithm's running time. Furthermore, we obtain matching upper and lower bounds of Θ(*n**m*^{2}(1 + log (*n*/*m*))) when the two trees have sizes*m*and*n*where*m*<*n*. **Availability**:- The paper is available in PostScript (1308k), gzipped PostScript (463k), and PDF (504k).
- See information on file formats.
- [Google Scholar search]

See also other papers by Erik Demaine.

Last updated October 17, 2021 by Erik Demaine.