FIFO Push-Relabel

1웨이브#

활성 정점을 큐로 관리한다. 알고리즘을 웨이브(wave)의 연속으로 정의한다.

• W의 정점을 큐에서 꺼낸 순서대로 처리한다. 각 정점 u에 대해 Push 가능한 간선이 없어질 때까지 Push를 반복하거나, Push 가능한 간선이 없으면 Relabel한다.
• 새로 활성화된 정점은 이번 웨이브에 있었는지 여부와 무관하게 다음 웨이브에 추가한다.
• W의 정점을 모두 처리하면 웨이브가 끝난다.

2증명#

하나의 웨이브에는 중복 정점이 없으므로 비포화 푸시는 최대 |W| ≤ n번이다.

H = max{h(v) : v 활성}으로 두자. Relabel이 없는 웨이브에서 W의 모든 정점이 비포화 푸시되어 비활성화되고, 새로 활성화된 정점의 높이는 최대 max_u∈W h(u) − 1 = H − 1이다. 따라서 Relabel 없는 웨이브가 끝날 때마다 H가 최소 1 감소한다.

H의 총 증가량은 정점당 높이 상한이 2n−1이므로 O(n²)이다. H ≥ 0이 항상 성립하므로 Relabel 없는 웨이브는 O(n²)번이다. Relabel이 있는 웨이브는 총 Relabel 횟수 이하이므로 O(n²)이다. 따라서 웨이브 수는 O(n²).

비포화 푸시의 총 횟수는 n × O(n²) = O(n³)이므로 시간 복잡도는 O(n³)이다.