World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

A Cost Optimal Parallel Algorithm for Patience Sorting

    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
    • A. Aldous and P. Diaconis, BAMS: Bulletin of the American Mathematical society 36, 413 (1999), DOI: 10.1090/S0273-0979-99-00796-X. Crossref, ISIGoogle Scholar
    • S. N. Bespamyatnikh and M. Segal, Information Processing Letters 76(1–2), 7 (2000), DOI: 10.1016/S0020-0190(00)00124-1. Crossref, ISIGoogle Scholar
    • C. D.   Castanho et al. , 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
    • R. J. Cole, SIAM Journal on Computing 17(4), 770 (1988), DOI: 10.1137/0217049. Crossref, ISIGoogle Scholar
    • T. H.   Cormen et al. , 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
    • M. L. Fredman, Discrete Mathematics 11, 29 (1975), DOI: 10.1016/0012-365X(75)90103-X. Crossref, ISIGoogle 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 ) . CrossrefGoogle Scholar
    • D. E.   Knuth , Sorting and Searching , The Art of Computer Programming   3 ( Addison-Wesley , 1973 ) . Google Scholar
    • R. E. Ladner and M. J. Fisher, Journal of ACM 27, 831 (1980), DOI: 10.1145/322217.322232. Crossref, ISIGoogle Scholar
    • C. L. Mallows, 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
    • R. Uehara, International Journal of Foundations of Computer Science 10(4), 473 (1999), DOI: 10.1142/S0129054199000332. Link, ISIGoogle Scholar