「並列トポロジカル整列アルゴリズム」(Vol.45,No.4)

平成16年度論文賞受賞者の紹介

「並列トポロジカル整列アルゴリズム」(Vol.45,No.4)

[論文概要]
 トポロジカル整列の従来の並列アルゴリズムは,推移的閉包行列の計算方法をもとに,節点数の3乗のプロセッサ数を用いて,節点数の対数時間で処理することができるが,使用するプロセッサ数の削減は極めて困難で,これ以上のコストの削減は期待できない.本論文では,分割統治法に基づく設計法によって,従来の並列アルゴリズムに比べ実行時間では同等であるが,使用するプロセッサ数を大幅に減少することができる非常に効率のよい並列アルゴリズムを提案する.

[推薦理由]
 本論文は、無閉路有向グラフ(節点数n, 辺数m)に対するCREW-PRAM 計算機モデルにおける並列トポロジカル整列アルゴリズムを提案したものである。従来の方法は推移的閉方行列の計算に依存しているため、プロセッサ数を O(n3)から減少させることは困難であったが、本論文で提案されている手法では、推移的閉方行列によらず基本的アルゴリズムを並列化するため、プロセッサ数をO(n+m)に減少させることが可能になり、この点で新規性が高いと評価できる。また、時間計算量は従来の方法と漸近的に同等であることから、有用性も十分にある。さらに、論文としての記述も極めて精緻で、完成度が高い。これらの理由により、本論文を平成16年度論文賞に推薦する。

多田 昭雄君  1966年京都大学工学部数理工学科卒業.同年東京芝浦電気㈱(現㈱東芝)入社.1994年熊本工業大学(現崇城大学)講師.2004年熊本大学大学院自然科学研究科後期博士課程修了.現在崇城大学情報学部コンピュータシステムテクノロジー学科教授.博士(工学).アルゴリズムとデータ構造の設計と解析等に関心を持つ.電子情報通信学会会員.

右田 雅裕君  1994年熊本大学工学部電気情報工学科卒業.1996年同大学院工学研究科電気情報工学専攻修士課程修了.2000年同大学院自然科学研究科後期博士課程単位取得退学.現在熊本大学総合情報基盤センター助手.アルゴリズムとデータ構造の設計と解析等に関心を持つ.

中村 良三君  1968年熊本大学大学院修士課程修了.工学博士.1968年~1974年中部電力㈱.1975年熊本大学工学部.現在同大学工学部数理情報システム工学科教授.アルゴリズムとデータ構造の設計と解析等に関心を持つ.電子情報通信学会会員.