非循環グラフにおける支配関係の簡潔な検出算法

概要

論文の詳細を見る
本稿では, 非循環有向グラフ(DAG;Directed Acyclic Graph)で表される制御フローグラフに対し, その支配関係を求める簡潔な算法を報告する.この算法は, 頂点数N, 辺数Mのグラフに対して, 大きさNのスタックのプッシュとポップに基づき, N-1回のリダクションを繰り返す.リダクションの進行中に, 次のリダクション対象頂点を探す手続きはまったく必要としない.支配木と支配辺境の算出は, グラフに対する一連のチダクション操作がすべて終了したとき同時に完了する.本算法は計算量がO(N)の部分とO(M)の部分からなり, 前者についての計算量は算法からほとんど自明である.後者については, NおよびMに対して独立な, グラフの構造の差異による若干の変動はあるものの, 算法および計測の結果から, 実用のプログラムでは, ほぼMに比例し, O(M)であることが主張できる.SpecCFP92テストプログラムから約240本を選抜して実行した結果は, 統計的に, Mに対して, 多少のばらつきをともなう線形性を示し, 比例係数は平均1.5, 最大2.5であった.これは既発表の他の方法より約3倍高速である.
社団法人情報処理学会の論文
2002-01-15