A fast algorithm for optimal alignment between similar ordered trees
(2003) In Fundamenta Informaticae 56(12). p.105120 Abstract
 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... (More)
 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. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/297998
 author
 Jansson, Jesper ^{LU} and Lingas, Andrzej ^{LU}
 organization
 publishing date
 2003
 type
 Contribution to journal
 publication status
 published
 subject
 in
 Fundamenta Informaticae
 volume
 56
 issue
 12
 pages
 105  120
 publisher
 IOS Press
 external identifiers

 wos:000186087600007
 scopus:0141493759
 ISSN
 01692968
 project
 VR 20024049
 language
 English
 LU publication?
 yes
 id
 c767ed0eebe64d2e834a52c95b234d6b (old id 297998)
 date added to LUP
 20160401 15:31:27
 date last changed
 20200112 18:32:45
@article{c767ed0eebe64d2e834a52c95b234d6b, abstract = {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.}, author = {Jansson, Jesper and Lingas, Andrzej}, issn = {01692968}, language = {eng}, number = {12}, pages = {105120}, publisher = {IOS Press}, series = {Fundamenta Informaticae}, title = {A fast algorithm for optimal alignment between similar ordered trees}, volume = {56}, year = {2003}, }