有向グラフの強連結成分を求める並列アルゴリズム

概要

論文の詳細を見る
有向グラフ(節点数n,辺数m)の強連結成分を求める問題は,最も基本的なグラフ問題のひとつであり,従来の並列アルゴリズムは,CRCW-PRAM計算機モデルで0(n^3)個のプロセッサを用いて,O(logn)時間で実行するアルゴリズムがある.このアルゴリズムは推移的閉包行列の計算に依存しているので, O(n^3)個のプロセッサを減少させることは難しい.本稿では,CREW-PRAM計算機モデルのもとで,分割統治法と超節点法を用いて,有向グラフに対して効率よく強連結成分を求める並列アルゴリズムを提案する.具体的には,はじめに有向グラフを入出次数が高々1の節点からなる線形リストに分割し,その線形リスト上での強連結成分を求める.次に2つの部分グラフの組をそれぞれ作り,その部分グラフ間での強連結成分を求める.強連結成分は超節点法で管理し,再帰的に部分グラフの組を併合しながら,グラフ全体の強連結成分を求める並列アルゴリズムである.この提案するアルゴリズムの計算量はCREW-PRAM計算機モデルでプロセッサ数がO(n+m),計算時間がO(log^2m)である.
社団法人電子情報通信学会の論文
2003-12-15