Subcaterpillar isomorphism: subtree isomorphism restricted pattern trees to caterpillars

• Autorzy: Miyazaki Tomoya , Hirata Kouichi

Identyfikatory

DOI

10.15439/2022F113

• Konferencja: Federated Conference on Computer Science and Information Systems (17 ; 04-07.09.2022 ; Sofia, Bulgaria)
• Języki publikacji: EN

Abstrakty

EN

In this paper, we investigate a subcaterpillar isomorphism that is a problem, for a rooted labeled caterpillar P and a rooted labeled tree T, of determining whether or not there exists a subtree in T which is isomorphic to P. Then, we design two algorithms to solve the subcaterpillar isomorphism for a caterpillar P and a tree T in (i) O(p + tDhσ) time and O(Dh) space and in (ii) O(p + tDσ) time and O(D(h + H)) space, respectively. Here, p is the number of vertices in P, t is the number of vertices in T, h is the height of P, H is the height of T, σ is the number of alphabets for labels and D is the degree of T. Furthermore, we give experimental results of the two algorithms for artificial data and real data.

Słowa kluczowe

EN

computer science; vegetation; isomorphism

PL

informatyka; roślinność; izomorfizm

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2022
• Tom: Vol. 30
• Strony: 351--356
• Opis fizyczny: Bibliogr. 11 poz., il., tab., wz.

Twórcy

autor

Miyazaki Tomoya

• Graduate School of Computer Science and Systems Engineering 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. A. Abboud, A. Backurs, T. D. Hansen, V. v. Williams, O. Zamir: Subtree isomorphism revisited, ACM Trans. Algo. 14, 27 (2018). https://doi.org/10.1145/3093239.
• 2. 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.
• 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/2
• 5. J. E. Hopcroft, R. M. Karp: An n algorithm for maximum matching in bipartite graphs, SIAM J. Comput. 2, 225–231 (1973). https://doi.org/10.1137/10.1137/0202019.
• 6. P. Kilpeläinen, H. Mannila: Ordered and unordered tree inclusion, SIAM J. Comput. 24, 340–356 (1995). https://doi.org/10.1137/S0097539791218202.
• 7. T. Miyazaki, M. Hagihara, K. Hirata: Caterpillar inclusion: Inclusion problem for rooted labeled caterpillars, Proc. ICPRAM’22, 280–287 (2022). https://doi.org/10.5220/0010826300003122.
• 8. K. Muraka, T. Yoshino, K. Hirata: Computing edit distance be tween 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 hori zontal distance to approximate edit distance for rooted labeled caterpillars, Proc. ICPRAM’19, 590–597 (2019). https://dx.doi.org/10.5220/0007387205900597.
• 10. R. Shamir, D. Tsur: Faster subtree isomorphism, J. Algo. 33, 267–280 (1999). https://doi.org/10.1006/jagm.1999.1044.
• 11. 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.

Uwagi

1. Track 6: 15th International Workshop on Computational Optimization

2. Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023).