WEKO3
アイテム
An O(n(n<sub>2</sub>/(p)+log p)) Parallel Algorithm to Compute the All Pairs Shortest Paths and the Transitive Closure
https://ipsj.ixsq.nii.ac.jp/records/59778
https://ipsj.ixsq.nii.ac.jp/records/59778016da952-2c59-458b-b6af-2f08f36c3f0e
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-JIP1202002.pdf (658.9 kB)
|
Copyright (c) 1989 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | JInfP(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 1989-08-25 | |||||||
| タイトル | ||||||||
| タイトル | An O(n(n<sub>2</sub>/(p)+log p)) Parallel Algorithm to Compute the All Pairs Shortest Paths and the Transitive Closure | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | An O(n(n<sub>2</sub>/(p)+log p)) Parallel Algorithm to Compute the All Pairs Shortest Paths and the Transitive Closure | |||||||
| 言語 | ||||||||
| 言語 | eng | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||
| 資源タイプ | journal article | |||||||
| 著者所属 | ||||||||
| Department of Computer Science Ibaraki University | ||||||||
| 著者所属 | ||||||||
| Department of Computer Science Ibaraki University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Computer Science, Ibaraki University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Computer Science, Ibaraki University | ||||||||
| 著者名 |
Ma, Jun
× Ma, Jun
|
|||||||
| 著者名(英) |
Ma, Jun
× Ma, Jun
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | Multiprocessors with shared memory structured as a complete binary tree are considered for use with a parallel algorithm to compute the all pairs shortest paths and the reflexive transitive closure in a weighted directed graph. The time complexity of the parallel algorithm is O(n(n^2/(p)+logp)) where n is the number of vertices in the graph and p(≤n^2) is the number of processors used. The Ada language is used to implement the algorithm. | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | Multiprocessors with shared memory structured as a complete binary tree are considered for use with a parallel algorithm to compute the all pairs shortest paths and the reflexive transitive closure in a weighted directed graph. The time complexity of the parallel algorithm is O(n(n^2/(p)+logp)), where n is the number of vertices in the graph and p(≤n^2) is the number of processors used. The Ada language is used to implement the algorithm. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AA00700121 | |||||||
| 書誌情報 |
Journal of Information Processing 巻 12, 号 2, p. 119-124, 発行日 1989-08-25 |
|||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 1882-6652 | |||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
