有向加重グラフが与えられた場合、頂点のすべてのペア間の最大フロー(または最小エッジ カット) を見つける方法。
単純なアプローチは、ペアごとにの複雑さを持つ Dinic のようなMax Flowアルゴリズムを呼び出すだけです。
したがって、すべてのペアで です。O((V^2)*E)O((V^4)*E)
O((V^3)*E)いくつかO(V^3)の最適化によって複雑さを軽減することは可能ですか?
質問する
2501 次
有向加重グラフが与えられた場合、頂点のすべてのペア間の最大フロー(または最小エッジ カット) を見つける方法。
単純なアプローチは、ペアごとにの複雑さを持つ Dinic のようなMax Flowアルゴリズムを呼び出すだけです。
したがって、すべてのペアで です。O((V^2)*E)O((V^4)*E)
O((V^3)*E)いくつかO(V^3)の最適化によって複雑さを軽減することは可能ですか?