「非循環グラフにおける支配関係の簡潔な検出算法」（Vol.43,No.SIG1(PRO13)）

［論文概要］
　本論文は，非循環なフローグラフの支配関係を求める簡潔高速な算法を紹介する．この算法は頂点数N辺数Mのグラフに対して，大きさNのスタックを用い，支配木と支配辺境の算出を，グラフに対するN-1回のリダクションと同時に実行する．リダクション対象頂点の番号は，リダクションの進行中にスタックに貯えられる．本算法の計算量は大部分がO(M)の部分からなり，SPEC CFP92から約240題を選抜して評価した結果，計算量は統計的にMに対して多少のばらつきを伴なう線形性を示し，比例係数は平均1.5，最大2.5であった．これは既発表の他の方法より約3倍高速である．

［推薦理由］
　本論文は，コンパイラ最適化における重要な基礎技術である非循環グラフの支配関係（可約なグラフの支配関係と実質的に等価）の検出問題に対して，簡潔かつ実用的に高速な線形時間アルゴリズムを与えている．この問題の高速アルゴリズムの構成は自明ではなく，比較的最近まで多くの研究が行われてきたが，本論文は後継頂点集合とスタックを用いる手法によって簡潔なアルゴリズムを導いた．これにより計算量の線形性が明確になったばかりでなく，定数係数も改善された．実験的評価も綿密に行われている．著者らはさらに，この結果を非可約なグラフに一般化した結果を後に得ている．論文の記述も厳密かつ明快であり，本論文は論文賞にふさわしいものと判断する．