WEKO3
アイテム
Polynomially Fast Parallel Algorithms for Some P-Complete Problems
https://nitech.repo.nii.ac.jp/records/4949
https://nitech.repo.nii.ac.jp/records/49499bee0c16-eddc-4147-aad7-908e72f1bf59
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
本文_fulltext (677.5 kB)
|
Copyright (c) 2001 IEICE http://search.ieice.org/index.html
|
| Item type | 学術雑誌論文 / Journal Article(1) | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2013-06-25 | |||||||||||||
| タイトル | ||||||||||||||
| タイトル | Polynomially Fast Parallel Algorithms for Some P-Complete Problems | |||||||||||||
| 言語 | en | |||||||||||||
| 言語 | ||||||||||||||
| 言語 | eng | |||||||||||||
| 資源タイプ | ||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||||
| 資源タイプ | journal article | |||||||||||||
| 著者 |
Castanho, Carla Denise
× Castanho, Carla Denise
× Chen, Wei
× Wada, Koichi
× Fujiwara, Akihiro
|
|||||||||||||
| 著者別名 | ||||||||||||||
| 姓名 | 和田, 幸一 | |||||||||||||
| bibliographic_information |
en : IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 巻 E84-A, 号 5, p. 1244-1255, 発行日 2001-05-01 |
|||||||||||||
| 出版者 | ||||||||||||||
| 出版者 | Institute of Electronics, Information and Communication Engineers | |||||||||||||
| 言語 | en | |||||||||||||
| ISSN | ||||||||||||||
| 収録物識別子タイプ | ISSN | |||||||||||||
| 収録物識別子 | 0916-8508 | |||||||||||||
| item_10001_source_id_32 | ||||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||||
| 収録物識別子 | AA10826239 | |||||||||||||
| 出版タイプ | ||||||||||||||
| 出版タイプ | VoR | |||||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||||||||||
| 内容記述 | ||||||||||||||
| 内容記述タイプ | Other | |||||||||||||
| 内容記述 | P-complete problems seem to have no parallel algorithm which runs in polylogarithmic time using a polynomial number of processors. A P-complete problem is in the class EP (Efficient and Polynomially fast) if and only if there exists a cost optimal algorithm to solve it in T(n) = O(t(n)ε) (ε < 1) using P(n) processors such that T(n) P(n) = O(t(n)), where t(n) is the time complexity of the fastest sequential algorithm which solves the problem. The goal of our research is to find EP parallel algorithms for some P-complete problems. In this paper first we consider the convex layers problem. We give an algorithm for computing the convex layers of a set S of n points in the plane. Let k be the number of the convex layers of S. When 1 k nε/2 (0 ε < 1) our algorithm runs in O((n log n)/p) time using p processors, where 1 p n1-ε/2, and it is cost optimal. Next, we consider the envelope layers problem of a set S of n line segments in the plane. Let k be the number of the envelope layers of S. When 1 k nε/2 (0 ε < 1), we propose an algorithm for computing the envelope layers of S in O((n α(n) log3 n)/p) time using p processors, where 1 p n1-ε/2, and α(n) is the functional inverse of Ackermann's function which grows extremely slowly. The computational model we use in this paper is the CREW-PRAM. Our first algorithm, for the convex layers problem, belongs to EP, and the second one, for the envelope layers problem, belongs to the class EP if a small factor of log n is ignored. | |||||||||||||
| 言語 | en | |||||||||||||
