Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Fundamenta Informaticae

1 2003

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: algorithm of Jiang, Wang, and Zhang

Sortuj według:

Ogranicz wyniki do:

A Fast Algorithm for Optimal Alignment between Similar Ordered Trees

Jansson J., Lingas A.

Fundamenta Informaticae

2003

Vol. 56, nr 1,2

105-120

We present a fast algorithm for optimal alignment between two similar ordered trees with node labels. Let S and T be two such trees with |S| and |T| nodes, respectively. If there exists an optimal alignment between S and T which uses at most d blank symbols and d is known in advance, it can be constructed in O(n logn ź(maxdeg)3 źd2) time, where n = max{|S|,|T|} and maxdeg is the maximum degree of all nodes in S and T. If d is not known in advance, we can construct an optimal alignment in O(n logn ź(maxdeg)3źf2) time, where f is the difference between the highest possible score for any alignment between two trees having a total of |S| + |T| nodes and the score of an optimal alignment between S and T, if the scoring scheme satisfies some natural assumptions. In particular, if the degrees of both input trees are bounded by a constant, the running times reduce to O(n logn źd2) and O(n logn źf2), respectively.