최대 흐름 알고리즘을 사용하여 네트워크의 에지 연결 찾기

Question

최대 흐름 알고리즘 (Edmond Karp/Ford-Fulkerson 알고리즘을 사용하여 방향없는 그래프의 가장자리 연결 (즉, 그래프 연결을 끊기 위해 제거 할 최소 가장자리 수)을 찾고 싶습니다.),

내가 그래프의 모든 두 노드 사이의 최소 최대 유량을 발견하여이 작업을 수행 할 수 있다는 것을 알고 있지만,이 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 |) 시간 동안 만 최대 흐름 알고리즘을 실행합니다.

Answer 1

그래프에서 노드 v을 구별합니다. 계산은 w이 v이 아닌 경우 최대 흐름은 v에서 w입니다. v은 그래프의 글로벌 최소 컷의 한 해안에 있어야하고 다른 것은 다른면에 있어야하므로이 플로우 중 하나가 전역 최소 컷을 식별합니다.

프리 플로우 푸시 알고리즘을 사용하면 글로벌 최소 컷 계산에 최소 (s, t) 컷 문제만큼 많은 시간이 소요되는 Hao와 Orlin의 트릭이 있습니다. 실용적인 이점이 있습니다. Karger는 O (n polylog (n)) 시간에 알고리즘을 수행하는 무작위 알고리즘을 가지고 있지만 빠른 구현은 물론 모든 구현을 알지 못합니다.