疎な有向グラフの強連結成分を求める効率良い並列アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
有向グラフ(節点数n, 辺数m)の強連結成分を求める問題は、最も基本的なグラフ問題の一つであり、現段階での最良の結果はCREW-PRAM並列計算機モデルで、O(n^3)台のプロセッサを用いて、O(log^2n)時間を実現したアルゴリズムである。これらのアルゴリズムは、行列の計算に依存しているので、O(n^3)台のプロセッサ数を下げることは困難である。また、辺の密度が低い疎グラフにおいては、行列計算や行列領域に無駄が発生する。本稿では、疎な有向グラフに対して、分割統治法と超節点法で効率良く強連結成分を求める並列アルゴリズムを提案する。このアルゴリズムはCREW-PRAM並列計算機モデルの上で、プロセッサ数がO(n)、計算時間がO(log^2n)である。
- 一般社団法人情報処理学会の論文
- 1999-01-27
著者
-
多田 昭雄
崇城大学情報学部コンピュータシステムテクノロジー学科
-
多田 昭雄
熊本工業大学
-
中村 良三
熊本大学工学部
-
中村 良三
熊本大学工学部数理情報システム工学科
-
中村 良三
熊本大学工学部電気情報工学科
関連論文
- 電子新聞に対する動的クラスタリング手法の提案
- 個人属性を考慮した情報フィルタリング
- ユーザの好みを考慮した新聞記事のランキング
- マルチエージェントによる新聞記事のランキング方式の提案
- 線形法における探索アルゴリズムの解析
- 分離連鎖法における挿入・探索アルゴリズムの解析
- キャッシュコヒーレンスプロトコルにおけるオーナーシップに関する考察
- キャッシュコヒーレンスプロトコルに対する一考察
- PERTチャートにおけるクリティカルパスを求める並列アルゴリズム(アルゴリズム理論)
- 式の自動分割による並列化アルゴリズム