## Computing Edit Distance between Rooted Labeled Caterpillars

### Kohei Muraka, Takuya Yoshino, Kouichi Hirata

DOI: http://dx.doi.org/10.15439/2018F179

Citation: Proceedings of the 2018 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 15, pages 249–255 (2018)

Abstract. 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(\lambda^2 h^2) time, where \lambda and h are the maximum number of leaves and the maximum height in two caterpillars, respectively.

### References

- T. Akutsu, D. Fukagawa, M. M. Halldórsson, A. Takasu, K. Tanaka: Approximation and parameterized algorithms for common subtrees and edit distance between unordered trees, Theoret. Comput. Sci. 470, 10–22 (2013).
- M. M. Deza, E. Deza: Encyclopedia of distances (4th ed.) Springer, 2016
- J. A. Gallian: A dynamic survey of graph labeling, Electorn. J. Combin. 14, DS6 (2007).
- K. Hirata, Y. Yamamoto, T. Kuboyama: Improved MAX SNP-hard results for finding an edit distance between unordered trees, Proc. CPM’11, LNCS 6661, 402–415 (2011).
- T. Jiang, L. Wang, K. Zhang: Alignment of trees – an alternative to tree edit, Theoret. Comput. Sci. 143, 137–148 (1995).
- T. Kawaguchi, T. Yoshino, K. Hirata: Path histogram distance for rooted labeled caterpillars, Proc. ACIIDS’18, LNAI 10751, 276–286 (2018).
- T. Kuboyama: Matching and learning in trees, Ph.D thesis, University of Tokyo (2007).
- L. S. Sterling, E. Y. Shapiro: The art of Prolog (2nd edition), The MIT Press (1994).
- K.-C. Tai: The tree-to-tree correction problem, J. ACM 26, 422–433 (1979).
- Y. Yamamoto, K. Hirata, T. Kuboyama: Tractable and intractable variations of unordered tree edit distance, Internat. J. Found. Comput. Sci. 25, 307–330 (2014).
- T. Yoshino, K. Hirata: Tai mapping hierarchy for rooted labeled trees through common subforest, Theory Comput. Sys. 60, 759–783 (2017).
- K. Zhang: A constrained edit distance between unordered labeled trees, Algorithmica 15, 205–222 (1996).
- K. Zhang, T. Jiang: Some MAX SNP-hard results concerning unordered labeled trees, Inform. Process. Lett. 49, 249–254 (1994).
- K. Zhang, J. Wang, D. Shasha: On the editing distance between undirected acyclic graphs, Internat. J. Found. Comput. Sci. 7, 45–58 (1996).