Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 19

Position Papers of the 2019 Federated Conference on Computer Science and Information Systems

Alignment for Rooted Labeled Caterpillars

, ,

DOI: http://dx.doi.org/10.15439/2019F338

Citation: Position Papers of the 2019 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 19, pages 19–25 ()

Full text

Abstract. A rooted labeled caterpillar (caterpillars, for short) is a rooted labeled tree transformed to a rooted path after removing all the leaves in it. In this paper, we design the algorithm to compute the alignment distance between caterpillars in O(h^2\lambda^3) time under the general cost function and in O(h^2\lambda) time under the unit cost function, where h is the maximum height and \lambda is the maximum number of leaves in caterpillars.

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). https://doi.org/10.1016/j.tcs.2012.11.017.
  2. M. M. Deza, E. Deza: Encyclopedia of distances (4th ed.) Springer (2016). https://doi.org/10.1007/978-3-662-52844-0.
  3. J. A. Gallian: A dynamic survey of graph labeling, Electorn. J. Combin., DS6 (2018).
  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). https://doi.org/10.1007/978-3-642-21458-5 34.
  5. T. Jiang, L. Wang, K. Zhang: Alignment of trees – an alternative to tree edit, Theoret. Comput. Sci. 143, 137–148 (1995). https://doi.org/10.1016/0304-3975(95)80029-9.
  6. T. Kuboyama: Matching and learning in trees, Ph.D thesis, University of Tokyo (2007).
  7. C. L. Lu, Z.-Y. Su, C. Y. Yang: A new measure of edit distance between labeled trees, Proc. COCOON’01, LNCS 2108, 338–348 (2001). https://doi.org/10.1007/3-540-44679-6 37.
  8. K. Muraka, T. Yoshino, K. Hirata: Computing edit distance between rooted labeled caterpillars, Proc. FedCSIS’18, 245–252 (2018). http://dx.doi.org/10.15439/2018F179.
  9. K. Muraka, T. Yoshino, K. Hirata: Vertical and horizontal distance to approximate edit distance for rooted labeled caterpillars, Proc. ICPRAM’19, 590–597 (2019). https://dx.doi.org/10.5220/0007387205900597.
  10. K.-C. Tai: The tree-to-tree correction problem, J. ACM 26, 422–433 (1979). https://doi.org/10.1145/322139.322143.
  11. J. T. L. Wang, K. Zhang: Finding similar consensus between trees: An algorithm and a distance hierarchy, Pattern Recog. 34, 127–137 (2001). https://doi.org/10.1016/50031-3203(99)00199-5.
  12. Y. Yamamoto, K. Hirata, T. Kuboyama: Tractable and intractable variations of unordered tree edit distance, Internat. J. Found. Comput. Sci. 25, 307–330 (2014). https://doi.org/10.1142/50129054114500154.
  13. T. Yoshino, K. Hirata: Tai mapping hierarchy for rooted labeled trees through common subforest, Theory Comput. Sys. 60, 759–783 (2017). https://doi.org/10.1007/s00224-016-9705-1.
  14. K. Zhang: A constrained edit distance between unordered labeled trees, Algorithmica 15, 205–222 (1996). https://doi.org/10.1007/BF01975866.
  15. K. Zhang, T. Jiang: Some MAX SNP-hard results concerning unordered labeled trees, Inform. Process. Lett. 49, 249–254 (1994). https://doi.org/10.1016/0020-0190(94)90062-0.
  16. K. Zhang, J. Wang, D. Shasha: On the editing distance between undirected acyclic graphs, Internat. J. Found. Comput. Sci. 7, 45–58 (1996). https://doi.org/10.1142/S0129054196000051.