Name
Abstract | ||
|---|---|---|
The edit distance between two ordered trees with vertex labels is the min- imum cost of transforming one tree into the other by a sequence of elementary op- erations consisting of deleting and relabel- ing 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 (6). Our result requires a novel adaptive strategy for deciding how a dynamic program divides into subproblems (which is interesting in its own right), to- gether with a deeper understanding of the previous algorithms for the problem. We also prove the optimality of our algorithm among the family of decomposition strategy algorithms—which also includes the previ- ous fastest algorithms—by tightening the known lower bound of (n2 log2 n) (4) to (n3), matching our algorithm's running time. Furthermore, we obtain matching up- per and lower bounds of �(nm2(1+log n m)) when the two trees have different sizes m and n, where m < n. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1145/1644015.1644017 | Clinical Orthopaedics and Related Research |
Keywords | DocType | Volume |
data structure,edit distance,lower bound | Journal | abs/cs/060 |
Issue | ISSN | Citations |
1 | ACM Transactions on Algorithms 6(1): (2009) | 15 |
PageRank | References | Authors |
0.66 | 6 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Erik D. Demaine | 1 | 4624 | 388.59 |
| Shay Mozes | 2 | 292 | 22.87 |
| Benjamin Rossman | 3 | 298 | 20.00 |
| Oren Weimann | 4 | 545 | 37.11 |