Proceedings of the 17th Conference on Computer Science and Intelligence Systems

DOI: http://dx.doi.org/10.15439/2022F113

Citation: Proceedings of the 17th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 30, pages 351–356 (2022)

Full text

Abstract. In this paper, we investigate a subcaterpillar isomorphism that is a problem for a rooted labeled caterpillar and a rooted labeled tree of determining whether or not there exists a subtree in the tree which is isomorphic to the caterpillar.Then, we design two algorithms to solve the subcaterpillar isomorphism for a caterpillar P and a tree T in O(p+tDh\sigma) time and O(Dh) space and in O(p+tD\sigma) 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 \sigma is the number of alphabets for labels, and D is the degree of T. Furthermore, we give experimental results of two algorithms for artificial data and real data.

References

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.