Computing Edit Distance between Rooted Labeled Caterpillars
Kohei Muraka, Takuya Yoshino, Kouichi Hirata · Annals of Computer Science and Information Systems · 2018
A rooted labeled caterpillar is a rooted labeled tree transformed to a path after removing all the leaves in it.In this paper, we design the algorithm to compute the edit distance between rooted labeled caterpillars in O(λ 2 h 2 ) time, where λ and h are the maximum number of leaves and the maximum height in two caterpillars, respectively.