Paper by Erik D. Demaine
- 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.
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(n3)-time algorithm for this problem, 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
algorithms—which also includes the previous fastest algorithms—by
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 of
Θ(n m2 (1 + log
(n/m))) when the two trees have sizes m and n
where m < n.
- 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.
These pages are generated automagically from a
Last updated May 13, 2021 by