A Cost Optimal Parallel Algorithm for Patience Sorting
Abstract
In this paper, we consider a parallel algorithm for the patience sorting. The problem is not known to be in the class NC or P-complete. We propose two algorithms for the patience sorting of n distinct integers. The first algorithm runs in
time using p processors on the EREW PRAM, where m is the number of decreasing subsequences in a solution of the patience sorting. The second algorithm runs in
time using p processors on the EREW PRAM. If
is satisfied, the second algorithm becomes cost optimal.
This research was partially supported by the Ministry of Education, Science, Sports and Culture, Grand-in-Air for Encouragement Scientists, 14780229, 2003.
References
-
A. V. Aho , J. E. Hopcroft and J. D. Ullman , The Design and Analysis of Computer Algorithms ( Addison-Wesley , 1974 ) . Google Scholar - BAMS: Bulletin of the American Mathematical society 36, 413 (1999), DOI: 10.1090/S0273-0979-99-00796-X. Crossref, ISI, Google Scholar
- Information Processing Letters 76(1–2), 7 (2000), DOI: 10.1016/S0020-0190(00)00124-1. Crossref, ISI, Google Scholar
-
C. D. Castanho , Polynomially fast parallel algorithms for some P-complete geometric problems , Proc. Workshop on Computational Geometry . Google Scholar C. Cerin , C. Dufourd and J. F. Myoupo , An efficient parallel solution for the longest increasing subsequence problem, Fifth International Conference on Computing and Information (ICCI'93) (IEEE Press, 1993) pp. 220–224. Google Scholar- SIAM Journal on Computing 17(4), 770 (1988), DOI: 10.1137/0217049. Crossref, ISI, Google Scholar
-
T. H. Cormen , Introduction to Algorithm , 2nd edn. ( The MIT Press , 2001 ) . Google Scholar F. Dehne , A. Fabri and A. Rau-Chaplin , ACM Symposium on Computational Geometry (1993) pp. 298–307. Google Scholar- Discrete Mathematics 11, 29 (1975), DOI: 10.1016/0012-365X(75)90103-X. Crossref, ISI, Google Scholar
T. Garcia , J. F. Myoupo and D. Semé , A work-optimal CGM algorithm for the longest increasing subsequence problem, The 2001 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA '01) (2001) pp. 563–569. Google Scholar-
R. Greenlaw , H. J. Hoover and W. L. Ruzzo , Limits to Parallel Computation: P-Completeness Theory ( Oxford university press , 1995 ) . Crossref, Google Scholar -
D. E. Knuth , Sorting and Searching ,The Art of Computer Programming 3 ( Addison-Wesley , 1973 ) . Google Scholar - Journal of ACM 27, 831 (1980), DOI: 10.1145/322217.322232. Crossref, ISI, Google Scholar
- Bulletin of the Institute of Mathematics and its Applications 9, 216 (1973). Google Scholar
T. Nakashima and A. Fujiwara , Parallelizability of the stack breadth-first search problem, The 2001 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA'01) (2001) pp. 722–727. Google Scholar- International Journal of Foundations of Computer Science 10(4), 473 (1999), DOI: 10.1142/S0129054199000332. Link, ISI, Google Scholar


