疎な有向グラフの強連結成分を求める効率良い並列アルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 1999-01-27
• タイトル: 疎な有向グラフの強連結成分を求める効率良い並列アルゴリズム
• タイトル / 言語: en
• タイトル: An Effective Parallel Algorithm for Finding Strongly Connected Components of a Sparse Directed Graph
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 熊本工業大学
• 著者所属: 熊本大学
• 著者所属(英): en
• 著者所属(英): Kumamoto Institute of Technology
• 著者所属(英): en
• 著者所属(英): Kumamoto University
• 著者名: 多田, 昭雄; 中村, 良三
• 著者名(英): Akio, Tada; Ryozo, Nakamura
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 有向グラフ（節点数n，辺数m）の強連結成分を求める問題は、最も基本的なグラフ問題の一つであり、現段階での最良の結果はCREW-PRAM並列計算機モデルで、O（n^3）台のプロセッサを用いて、O（log^2n）時間を実現したアルゴリズムである。これらのアルゴリズムは、行列の計算に依存しているので、0（n^3）台のプロセッサ数を下げることは困難である。また、辺の密度が低い疎グラフにおいては、行列計算や行列領域に無駄が発生する。本稿では、疎な有向グラフに対して、分割統治法と超節点法で効率良く強連結成分を求める並列アルゴリズムを提案する。このアルゴリズムはCREW-PRAM並列計算機モデルの上で、プロセッサ数が0（n）、計算時間がO（log^2n）である。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: A problem for finding strongly connected components of a directed graph is one of the most basic problems in graph theory. The best effective parallel algorithm is the one that takes O(log^2n) time using O(n^3) processors on a CREW-PRAM model so far. Because the complexity of the algorithm depends upon the matrix multiplication, it is difficult to reduce the number of processors futhermore. Specially in a sparse graph, a lot of wasteful processor time and memory space occur to matrix computations. This paper presents an efficient parallel algorithm for finding strongly connected components of a sparse directed graph, using devide and conquer technique and supernode method. This algorithm requires O(n) processors and O(log^2n) time on a CREW-PRAM model.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1999, 号 8(1998-AL-066), p. 65-72, 発行日 1999-01-27
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会