6

最大フロー アルゴリズム (Edmond Karp / Ford-Fulkerson アルゴリズム) を使用して、無向グラフのエッジ接続 (つまり、グラフを切断するために削除するエッジの最小数) を見つけたいです。

グラフの 2 つのノードごとに最小最大フローを見つけることでこのタスクを達成できることはわかっていますが、これにより O(|V| ^ 2) 個のフロー ネットワークが発生します。

int Edge-Connectivity(Graph G){
    int min = infinite;
    for (Vertex u: G.V){
        for (Vertex v: G.V){
           if (u != v){ 
             //create directed graph Guv (a graph with directed edges and source u and sink v)
             //run Edmonds-Karp algorithm to find the maximum flow |f*|
             if (min > |f*|)
               min = |f*|;
           }    
         }
     }
     return min;
}

しかし、私は |V| でこれをやりたいのです。フロー ネットワーク (O(|V| ^ 2) の代わりに O(|V|) 回だけ最大フロー アルゴリズムを実行)

4

1 に答える 1

7

vグラフ内のノードを区別します。w以外のすべてについてv、 から までの最大フローを計算vしwます。vグラフのグローバル ミニマム カットの一方の岸にある必要があり、他の何かが反対側にある必要があるため、これらのフローの 1 つがグローバル ミニマム カットを識別します。

Hao と Orlin によるトリックがあり、プリフロー プッシュ アルゴリズムを使用すると、グローバル最小カット計算に最小 (s,t) カット問題とほぼ同じ時間がかかります。実用的であるという利点があります。Karger には、O(n polylog(n)) 時間でそれを行うランダム化されたアルゴリズムがありますが、高速な実装は言うまでもなく、実装については知りません。

于 2013-05-05T12:46:12.377 に答える