Coarse-Grained Multicomputer Based-Parallel Algorithms for the Longest Common Subsequence Problem with a String-Exclusion Constraint

In this paper, new parallel algorithms based on the Coarse-Grained Multicomputer (CGM) model for solving the Longest Common Subsequence (LCS) problem with a string exclusion constraint (STR-EC-LCS) is presented. Based on a previous sequential algorithm, we propose two CGM parallel algorithms for STR-EC-LCS problem. We perform an experimental study of our two solutions to validate our theoretical predictions, and conclude that our first algorithm that minimizes idleness of the processors is better than the second. To the best of our knowledge, these algorithms are the first CGM- based parallel algorithms for the generalized-constrained-LCS problem.