無向グラフにおいて1つのオイラー小径を求める並列アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
オイラー小径を求める逐次アルゴリズムとしてフラーリーのアルゴリズムがあるが,効率良い並列アルゴリズムは見当たらない.本稿では,CREW-PRAM計算機モデルのもとで,無向連結グラフにおいて1つのオイラー小径を求める並列アルゴリズムを提案する.具体的には,はじめにグラフがオイラー小径をもつグラフか否かを判定する.次に,グラフの各節点の次数が高々2になるように節点をいくつかの新節点に分割し,そして新節点間を辺で連結して1つのオイラー小径を求める並列アルゴリズムである.提案する並列アルゴリズムの計算量は,節点数n,辺数mとするとき,プロセッサ数O(n+m)を用いて時間量がO(log(n+m))となる.
- 2008-05-20