WEKO3
アイテム
A Cost Optimal Parallel Algorithm for Patience Sorting
http://hdl.handle.net/10228/530
http://hdl.handle.net/10228/530a3b49363-d4ba-4d7b-932e-8edf739c5a26
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
S0129626406002459.pdf (258.3 kB)
|
|
| アイテムタイプ | 学術雑誌論文 = Journal Article(1) | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2007-12-18 | |||||||||||||
| 資源タイプ | ||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||||
| 資源タイプ | journal article | |||||||||||||
| タイトル | ||||||||||||||
| タイトル | A Cost Optimal Parallel Algorithm for Patience Sorting | |||||||||||||
| 言語 | en | |||||||||||||
| 言語 | ||||||||||||||
| 言語 | eng | |||||||||||||
| 著者 |
Nakashima, Takaaki
× Nakashima, Takaaki× 藤原, 暁宏
WEKO
1127
|
|||||||||||||
| 抄録 | ||||||||||||||
| 内容記述タイプ | 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 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. | |||||||||||||
| 書誌情報 |
Parallel Processing Letters (PPL) 巻 16, 号 1, p. 39-51, 発行日 2006-03 |
|||||||||||||
| 出版社 | ||||||||||||||
| 出版者 | World Scientific Publishing Company | |||||||||||||
| DOI | ||||||||||||||
| 関連タイプ | isVersionOf | |||||||||||||
| 識別子タイプ | DOI | |||||||||||||
| 関連識別子 | https://doi.org/10.1142/S0129626406002459 | |||||||||||||
| ISSN | ||||||||||||||
| 収録物識別子タイプ | PISSN | |||||||||||||
| 収録物識別子 | 0129-6264 | |||||||||||||
| 著作権関連情報 | ||||||||||||||
| 権利情報 | Copyright © World Scientific Publishing Company | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | Patience sorting | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | parallel algorithms | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | P-completeness | |||||||||||||
| 出版タイプ | ||||||||||||||
| 出版タイプ | AM | |||||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_ab4af688f83e57aa | |||||||||||||
| 査読の有無 | ||||||||||||||
| 値 | yes | |||||||||||||
| 情報源 | ||||||||||||||
| 識別子タイプ | URI | |||||||||||||
| 関連識別子 | http://www.worldscinet.com/ppl/ppl.shtml | |||||||||||||
| 関連名称 | http://www.worldscinet.com/ppl/ppl.shtml | |||||||||||||
