Subcaterpillar Isomorphism: Subtree Isomorphism Restricted Pattern Trees To Caterpillars

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.