オイラー経路の一つを求める並列アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
オイラー経路を求める逐次アルゴリズムとしてフラーリーのアルゴリズムがあるが、効率の良い並列アルゴリズムは見当たらない。本稿では、CREW-PRAM計算機モデルのもとで、オイラーグラフにおいて一つのオイラー経路を求める並列アルゴリズムを提案する。具体的には、はじめに、各辺が出節点と入節点で与えられた無向辺に辺番号を付与し、これに出節点と入節点を入れ換えた逆向き辺を追加して、節点番号と辺番号で整列する。そして、各節点において先頭から順に、2辺を1組として各辺を接続すると、複数の部分ループが構成される。次に、ブロードキャストを利用してこの部分ループ内の最少辺番号を特定する。この最少番号を持つ辺の節点において2つの部分ループを接続しつつ、一つのオイラー経路を求める並列アルゴリズムである。提案する並列アルゴリズムの計算量は、節点数n,辺数mとする時、プロセッサ数O(m),時間量がO(log^2 m)となる。
- 2009-01-23