Efficient Parallelization Using Rank Convergence in Dynamic Programming Algorithms
This paper proposes an efficient parallel algorithm for an important class of dynamic programming problems that includes Viterbi, Needleman-Wunsch, Smith-Waterman, and Longest Common Subsequence.