フローグラフの支配関係木を求めるアルゴリズムについての覚書 言語処理系を実装するとき、フローグラフの支配関係木(dominator tree)を求める必要が生じる。 このメモは、支配関係木を求める、あまり知られていないアルゴリズムについて記す。 この方法は理論的計算量の点では劣るものの、非常にシンプルであり実用上十分な性能を持つ。 準備 単一の入口rを持つ有向グラフGが与えられているとする。 G中の頂点v, wについて、rからwへ行くにはかならずvを通らなくてはならない場合、 vはwを支配する(v dominates w)という。この関係をv DOM wと書く。 関係 DOM は、半順序である(反射律(v DOM v)、反対称律(v DOM w かつ w DOM v なら v = w)、推移律 (v DOM w かつ w DOM u なら v DOM u)の3条件を満たす)。 そこで、この