Parallel algorithms for fast computation of normalized edit distances

The authors give work-optimal and polylogarithmic time parallel algorithms for solving the normalized edit distance problem. The normalized edit distance between two strings X and Y with lengths n⩾m is the minimum quotient of the sum of the costs of edit operations transforming X into Y by the length of the edit path corresponding to those edit operations. Marzal and Vidal (1993) proposed a sequential algorithm with a time complexity of O(nm²). They show that this algorithm can be parallelized work-optimally on an array of n (or m) processors, and on a mesh of n×m processors. They then propose a sublinear time algorithm that is almost work-optimal: using O(mn^1.75) processors, the time complexity of the algorithm is O(n^0.75 log n) and the total number of operations is O (mn ^2.5 log n). This algorithm runs on a CREW PRAM, but is likely to work on weaker PRAM models and hypercubes with minor modifications. Finally, they present a polylogarithmic O(log² n) time algorithm based on matrix multiplication which runs on a O(n⁶/log n) processor hypercube