Math @ Duke

Publications [#348696] of Benjamin Rossman
Papers Published
 Demaine, ED; Mozes, S; Rossman, B; Weimann, O, An optimal decomposition algorithm for tree edit distance,
Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4596 LNCS
(January, 2007),
pp. 146157, ISBN 3540734198 [doi]
(last updated on 2022/05/21)
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 worstcase O(n 3)time algorithm for this problem, improving the previous best O(n3 log n)time algorithm [7]. 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 Q(n2 log2 n) [4] to Ωn 3), matching our algorithm's running time. Furthermore, we obtain matching upper and lower bounds of ⊖(nm2(1 + log m/n)) when the two trees have sizes m and n where m < n. © SpringerVerlag Berlin Heidelberg 2007.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

