1

平面グラフの最小カットを見つけるアルゴリズムを知っています。

O(NlogN)として動作

各頂点がオリジナルのグラフ ファセットに対応し、エッジが 2 つのファセットを接続する最小エッジに対応する双対グラフを作成します。

次に、ダイクストラを使用して、このグラフの最小パスを見つけます。

このようにして、最小カットを見つけてフロー値をカウントすることができます。

しかし、このフロー値を提供する元のグラフ エッジのセットを見つけるにはどうすればよいでしょうか?

4

1 に答える 1

3

あなたが説明しているアルゴリズムは、無向グラフ（Reifのアルゴリズム）でのみ機能します。Hassin と Johnson は、それを拡張して最大フローを計算する方法を示しました。最近、これらのアルゴリズムを O(n loglog n) 時間で実装できることが示されました。GF Italiano、Y. Nussbaum、P. Sankowski、および C. Wulff-Nilsen の無向平面グラフの最小カットおよび最大フローの改善されたアルゴリズムを参照してください。Proc。コンピューティング理論に関する第 43 回 ACM シンポジウム (STOC)、サンノゼ、2011 年。

有向平面グラフでは、 知られている最速のアルゴリズムは O(n log n) で実行され ます。 cs.uiuc.edu/~jeffe/pubs/parshort.html

于 2012-05-19T19:44:14.513 に答える