The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

A fast algorithm for optimal alignment between similar ordered trees

På svenska

Author

Summary, in English

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 log n (.) (maxdeg)(3) (.) d(2)) 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 log n (.) (maxdeg)(3 .) f(2)) 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 log n (.) d(2)) and O(n log n (.) f(2)), respectively.

Department/s

  • Computer Science

Publishing year

2003

Language

English

Pages

105-120

Publication/Series

Fundamenta Informaticae

Volume

56

Issue

1-2

Document type

Journal article

Publisher

IOS Press

Topic

  • Computer Science

Status

Published

Project

  • VR 2002-4049

ISBN/ISSN/Other

  • ISSN: 0169-2968