Summary: 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 [P. N. Klein, “Computing the edit-distance between unrooted ordered trees”, Lect. Notes Comput. Sci. 1461, 91–102 (1998; Zbl 0932.68066)]. 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 \(\Omega (n ^{2}\log^{2} n)\) to \(\Omega (n ^{3})\), matching our algorithm’s running time. Furthermore, we obtain matching upper and lower bounds of \(\Theta(n m^2 (1 + \log \frac{n}{m}))\) when the two trees have sizes \(m\) and \(n\) where \(m < n\).
For the entire collection see [Zbl 1119.68002].