A fast algorithm for optimal alignment between similar ordered trees
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