Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Annals of Computer Science and Information Systems

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Subcaterpillar Isomorphism: Subtree Isomorphism Restricted Pattern Trees To Caterpillars

Miyazaki Tomoya, Hirata Kouichi

Annals of Computer Science and Information Systems

2022

Vol. 30

351--356

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.

Alignment for rooted labeled caterpillars

Ukita Yoshiyuki, Yoshino Takuya, Hirata Kouichi

Annals of Computer Science and Information Systems

2019

Vol. 19

19--25

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.