有向グラフの遷移的削減

我々は、有向グラフの経済的な経路情報の表現を考察する。有向グラフ Gᵗ は、有向グラフ G の遷移的削減であると言われる条件は、(i) Gᵗ が頂点 u から頂点 v への有向経路を持つのは、G が頂点 u から頂点 v への有向経路を持つ場合に限る、そして (ii) 条件 (i) を満たす Gᵗ よりも弧の数が少ないグラフは存在しないこと。サイクルを持つ有向グラフは、このような表現が複数存在することがあるが、我々はそのようなグラフの遷移的削減として自然な標準表現を選択することにする。最適なアルゴリズムがグラフの遷移的削減を見つける場合の時間計算量は、グラフの遷移的閉包を計算する場合やブール行列の乗算を行う場合の時間と同じであることが示されている。