Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 15

Proceedings of the 2018 Federated Conference on Computer Science and Information Systems

Computing Edit Distance between Rooted Labeled Caterpillars

, ,

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 ()

Full text

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

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