The Prague Stringology Conference 2006

Gad M. Landau

Can Dist Tables Be Merged in Linear Time – An Open Problem

Dist tables are key players in the computation of dynamic programming tables in o(n2) time. Given two strings A and T, dist(A,T) stores the scores of the edit distances between T and all substrings of A. Given dist(A,T) and dist(B,T) (strings A and B are each of length m and T is of length n) the best known algorithms that compute dist(AB,T) run in O(nm) time or O(n1.5) time. We will discuss the use of dist tables and Schmidt and Tiskin's Algorithms as well as some thoughts on possible directions to answering the open problem.

Download paper: Article in PostScript Article in PDF BibTeX Reference
 PostScript   PDF   BibTeX reference 
Download presentation: Presentation