「並列トポロジカル整列アルゴリズム」（Vol.45，No.4）

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

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