@article{oai:kyutech.repo.nii.ac.jp:00000260,
 author = {Nakashima, Takaaki and Fujiwara, Akihiro and 藤原, 暁宏},
 issue = {1},
 journal = {Parallel Processing Letters (PPL)},
 month = {Mar},
 note = {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 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. The second algorithm runs in O(log n+n log n/p+m2log n/p+m log p)time using p processors on the EREW PRAM. If 1<p<n/m2 is satisfied, the second algorithm becomes cost optimal.},
 pages = {39--51},
 title = {A Cost Optimal Parallel Algorithm for Patience Sorting},
 volume = {16},
 year = {2006},
 yomi = {フジワラ, アキヒロ}
}