An optimal decomposition algorithm for tree edit distance


Conference Paper

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(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 algorithms-which also includes the previous fastest algorithms-by 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. © Springer-Verlag Berlin Heidelberg 2007.

Full Text

Duke Authors

Cited Authors

  • Demaine, ED; Mozes, S; Rossman, B; Weimann, O

Published Date

  • January 1, 2007

Published In

Volume / Issue

  • 4596 LNCS /

Start / End Page

  • 146 - 157

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

International Standard Book Number 10 (ISBN-10)

  • 3540734198

International Standard Book Number 13 (ISBN-13)

  • 9783540734192

Digital Object Identifier (DOI)

  • 10.1007/978-3-540-73420-8_15

Citation Source

  • Scopus