A CGM algorithm solving the longest increasing subsequence problem

In this paper, we consider parallel algorithm for the longest increasing subsequence problem. Although this problem is primitive combinatorial optimization problem, this is not known to be in the class NC or P-complete, that is, no NC algorithm have been proposed for this problem, and there is no proof which shows the problem is P-complete. We present a coarse grained parallel algorithm that solves the Longest Increasing Subsequence Problem shown as a basis for DNA comparison. It can be implemented in the CGM model with P processors in O(N log(2) N/P) time and O(P) communication steps for an input sequence of N integers. This algorithm is based on a new optimal and very simple sequential algorithm having a time complexity of O(N log(2) N).