オイラー経路の一つを求める並列アルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 2009-01-23
• タイトル: オイラー経路の一つを求める並列アルゴリズム
• タイトル / 言語: en
• タイトル: Parallel Algorithm for Finding an Eulerian Path
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 崇城大学情報学部
• 著者所属: 崇城大学情報学部
• 著者所属(英): en
• 著者所属(英): Faculty of Computer and Information Sciences, Sojo University
• 著者所属(英): en
• 著者所属(英): Faculty of Computer and Information Sciences, Sojo University
• 著者名: 松本, 吉實; 多田, 昭雄
• 著者名(英): Yoshimi, Matsumoto; Akio, Tada
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: オイラー経路を求める逐次アルゴリズムとしてフラーリーのアルゴリズムがあるが、効率の良い並列アルゴリズムは見当たらない。本稿では、 CREW-PRAM 計算機モデルのもとで、オイラーグラフにおいて一つのオイラー経路を求める並列アルゴリズムを提案する。具体的には、はじめに、各辺が出節点と入節点で与えられた無向辺に辺番号を付与し、これに出節点と入節点を入れ換えた逆向き辺を追加して、節点番号と辺番号で整列する。そして、各節点において先頭から順に、 2 辺を 1 組として各辺を接続すると、複数の部分ループが構成される。次に、ブロードキャストを利用してこの部分ループ内の最少辺番号を特定する。この最少番号を持つ辺の節点において 2 つの部分ループを接続しつつ、一つのオイラー経路を求める並列アルゴリズムである。提案する並列アルゴリズムの計算量は、節点数 n , 辺数 m とする時、プロセッサ 数 O (m) ,時間量が O (log2 m) となる。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: There is Fleury’s algorithm as a sequential algorithm for finding an Eulerian path. However we cannot find a parallel algorithm for this problem. In this paper, we propose an efficient parallel algorithm for finding an Eulerian path in an undirected graph with n vertices and m edges on a CREW-PRAM model. Namely, the proposed algorithm initially gives an edge number for each edge which is composed of out-vertex number and in-vertex number, and appends reverse edges which changed out- and in- vertex number. Then these edges with vertex numbers and edge numbers are sorted. Next, after we connect a pair of two edges from the top for each vertex, then some partial loops are constructed. At last, these loops are joined into one Eulerian path. The proposed algorithm requires O (m) processors and O (log2 m) time.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2009, 号 9(2009-AL-122), p. 17-24, 発行日 2009-01-23
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会