CLRS 한글판을 보면 목차에 푸시-재명명, 재명명후-앞보내기 알고리즘이라고 있다. 뭔가 힙하고 새로워보이는 알고리즘같아 살펴보니 Push-Relabel을 한국어로 번역하다가 나온 이름이었다. (...) 그런 의미에서 이번 포스트에서는 Push-Relabel에 대해 알아본다. Push-Relabel도 1984년에 나온 비교적 최신 논문에 들어있다. SCC로 유명한 Tarjan이 저자로 있다! 해당 논문에 명시적으로 Push-Relabel이라는 알고리즘 이름은 없지만 전해 내려오면서 지어진 이름인 것 같다. 소개네트워크에서 전송 가능한 데이터를 계산하는 등 유량을 계산하는 것은 중요하다. Push-Relabel도 이러한 최대 유량을 구하는 알고리즘이며 $O(NM^2)$을 가지는 에드먼드 카프나 $O(N^2..
