Advertisement
Published in:
2007 | OriginalPaper | Chapter
An Optimal Decomposition Algorithm for Tree Edit Distance
Authors : Erik D. Demaine, Shay Mozes, Benjamin Rossman, Oren Weimann
Published in: Automata, Languages and Programming
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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 [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
Ω
(
n
2
log
2
n
) [4] to
Ω
(
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
.