講演抄録/キーワード |
講演名 |
2014-09-02 16:30
無閉路有向グラフの最短路を求める並列アルゴリズム ○右田雅裕・戸田真志(熊本大) COMP2014-23 |
抄録 |
(和) |
無閉路有向グラフDAG(n=節点数,m=辺数)において始点から各頂点への最短路長(単一始点最短路)を求める並列アルゴリズムを提案する.提案する並列アルゴリズムは,CREW-PRAMモデル上で分割統治法をもとに,プロセッサ数がO(n+m),時間量がO(log^2 m)となる計算量を持つ効率よい並列アルゴリズムである. |
(英) |
In this paper, we propose an efficient parallel algorithm for determining shortest paths in a DAG(Directed Acyclic Graph), based on a CREW-PRAM model. The proposed algorithm is based on a divide and conquer algorithm design technique on a CREW-PRAM model. In a DAG with the number of vertices n and the number of edges m, the proposed algorithm requires O(n+m) processors and O(log^2 m) times on a CREW-PRAM model. |
キーワード |
(和) |
DAG / 最短路 / 並列アルゴリズム / / / / / |
(英) |
DAG / Shortest Path / Parallel Algorithm / / / / / |
文献情報 |
信学技報, vol. 114, no. 199, COMP2014-23, pp. 55-59, 2014年9月. |
資料番号 |
COMP2014-23 |
発行日 |
2014-08-26 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2014-23 |