Subcaterpillar Isomorphism: Subtree Isomorphism Restricted Pattern Trees To Caterpillars

• Autorzy: Miyazaki Tomoya , Hirata Kouichi

Identyfikatory

DOI

10.15439/2022F113

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

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

Twórcy

autor

Miyazaki Tomoya

autor

Hirata Kouichi