T. Nakashima and A. Fujiwara (Japan)

patience sorting, longest increasing subsequence, parallelizability

In this paper, we consider parallel algorithms for the patience sorting and the longest increasing subsequence. These two problems are related each other and are not known to be in the class NC or P-complete. We ﬁrst propose two algorithms for the patience sorting of n distinct integers. The ﬁrst algorithm runs in O(m(n/p + log n)) time using p processors on the EREW PRAM, where m is the number of decreasing subsequences in a solution of the patience sorting, and the second algorithm runs in O(n log n / p + m^{2}log n /p + m log p) time using p processors on the EREW PRAM. If 1 < p < n /m^{2} is satisﬁed, the second algorithm becomes cost optimal. Finally, we propose a procedure which computes the longest increasing subsequence from a solution of the patience sorting, and obtain a parallel algorithm, which runs with the same complexity as the algorithm for the patience sorting, for the longest increasing subsequence.

Important Links:

Go Back