이하의 특성으로, Stoer-Wagner Algorithm 에 비해 장점이 없는것 같다. 그래서 굳이 몰라도 될거 같다
제약 있음: Unweighted graph에서만 사용 가능하다
Randomized 알고리즘 → 오답 확률 있음
속도 느림
구현 난이도 별차이 없음
기본적으로 Randomized 알고리즘이다. 한번 돌리는데에 O(ElogV)인데, 한번 돌려서 정답을 찾을 확률은 매우 낮다. 1/C(V,2) 의 확률.
그래서 엄청 많이 돌려야 정답을 기대할수 있다. O(V^2logV)번 돌리면 오답률이 1/V 이하로 낮아진다.
O(ElogV)알고리즘을 O(V^2logV)번 돌리려면 O(V^2*E*logV)가 걸린다. Karger–Stein algorithm 은 이것을 발전시켜서 O(V^2*log^3(V))로 속도를 향상시켰다. 하지만 그래도 O(V^3)인 Stoer-Wagner Algorithm에 비해 큰 메리트가 없다.
Edge-disjoint spanning tree 들에서 컷을 찾아내는 방식인데.. 이론적으로는 이쪽이 가장 빠르다고 한다. PS에서 쓸일은 아직 없어보인다.
State-of-art는 deterministic 알고리즘의 경우, unweighted graph에서는 O(E*log^2(V)*loglog^2(V)), weighted graph에서는 O(VE) 에 동작한다고 한다
Stoger-Wagner 알고리즘
mincut phase에서 s-t mincut을 찾고, 얻은 s,t를 contraction 하는 작업을 O(V)번 반복한다
이렇게 찾아진 mincut 값들중 최소값이 global mincut의 capacity이다
mincut phase는 프림 알고리즘과 비슷한 방식이라서, O(V^2) 또는 힙을 써서 O(ElogV)에 구현 가능. 그래서 총 시간복잡도는 O(V^3) 또는 O(VElogV)가 된다.
보통 프림이나 다익스트라는 sparse 한 그래프를 대상으로 돌리는 경우가 많아서, 힙을 쓰는 O(ElogV) 구현이 일반적이다. 하지만 글로벌 민컷 관련해서 백준에 있는 문제들은 대부분 E=O(V^2)인 dense graph이다. 그래서 백준에서 문제를 풀기에는 힙을 안쓰는 구현이 더 유용하다
mincut에 해당하는 엣지를 찾는 방법
보통 mincut의 capacity를 구하는 방법만 설명되어있고, mincut에 해당하는 엣지를 찾는 방법은 안 나와있는 경우도 많아서 찾는데 고생했다.
i번째의 mincut phase에서 구해진 s-t mincut의 용량이 값이 최소용량이었다고 하자. 이때의 t노드와 여태까지 (i-1번째 phase까지) t노드와 컨트랙션 되었던 노드들이 하나의 파티션을 이룬다. 당연히 이 노드들을 제외한 노드들이 다른 파티션을 이룬다. 이제 모든 엣지들 중에서 서로 다른 파티션의 노드들을 연결하는 엣지들만 찾으면 mincut의 엣지들이 된다.
실제 구현은 i-1번째 phase까지 컨트랙션되는 노드 쌍들을 엣지로 이어서 그래프를 만든 다음에 i번째 phase에서 찾은 t노드와 연결된 노드들을 모두 하나의 파티션으로 두면 된다. 그래프탐색을 해도 되고 Disjoint set을 이용해도 된다.
구현 및 관련문제
s-t민컷 문제와 마찬가지로, 구하는 값은 여러가지가 될수 있다
민컷의 캐퍼시티, 민컷에 포함하는 엣지들, 민컷으로 나뉘어진 두 노드 그룹
그래서 함수 하나로 만들기 보다는 그냥 클래스로 만들었다.
캐퍼시티만 구할때는, 그냥 contraction 한 노드쌍들을 리스트에 저장만 해둔다. partition이나 edge들을 구해야 할때는 저장해둔 contraction 히스토리를 Disjoint set으로 재구성해서 partition을 만든다.
O(n^3) 알고리즘이다 보니, 구현 디테일에 따라서 속도 차이가 좀 나는 편이다. 현재 백준에 스토어-바그너 태그로 들어있는 문제는 모두 4개인데, 이것들을 모두 풀기 위해서는 구현을 좀 신경써야 한다..