A Cost Optimal Parallel Algorithm for Patience Sorting
A Cost Optimal Parallel Algorithm for Patience Sorting
复制标题
一种成本最优的耐心排序并行算法
DOI：
--
复制
发表时间：
2006
影响因子：
0.4
通讯作者：
A. Fujiwara
中科院分区：
文献类型：
--
作者：
T. Nakashima;A. Fujiwara
在本文中，我们考虑一种用于耐心排序的并行算法。该问题是否属于NC类或P -完全类尚不清楚。我们针对n个不同整数的耐心排序提出了两种算法。第一种算法在EREW PRAM上使用p个处理器，运行时间为，其中m是耐心排序的一个解中递减子序列的数量。第二种算法在EREW PRAM上使用p个处理器，运行时间为。如果满足条件，第二种算法将成为成本最优算法。
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.