Alignment for rooted labeled caterpillars

• Autorzy: Ukita Yoshiyuki , Yoshino Takuya , Hirata Kouichi

Identyfikatory

DOI

10.15439/2019F338

• Konferencja: Federated Conference on Computer Science and Information Systems (14 ; 01-04.09.2019 ; Leipzig, Germany)
• Języki publikacji: EN

Abstrakty

EN

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(h2λ3) time under the general cost function and in O(h2λ) time under the unit cost function, where h is the maximum height and λ is the maximum number of leaves in caterpillars.

Słowa kluczowe

EN

data mining; edit distance; caterpillar; alignment distance; multisets

PL

eksploracja danych; odległość edycyjna; multizbiór

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2019
• Tom: Vol. 19
• Strony: 19--25
• Opis fizyczny: Bibliogr. 16 poz., wz., tab. rys.

Twórcy

autor

Ukita Yoshiyuki

• Graduate School of Computer Science and Systems Engineering, Kyushu Institute of Technology, Kawazu 680-4, Iizuka 820-8502, Japan

autor

Yoshino Takuya

• Department of Artificial Intelligence, Kyushu Institute of Technology, Kawazu 680-4, Iizuka 820-8502, Japan

autor

Hirata Kouichi

• Department of Artificial Intelligence, Kyushu Institute of Technology, Kawazu 680-4, Iizuka 820-8502, Japan

Bibliografia

• 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.

Uwagi

1. Track 1: Artificial Intelligence and Applications

2. Technical Session: 12th International Workshop on Computational Optimization

3. Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).