구사과

https://dl.acm.org/doi/pdf/10.5555/982792.982916 Cut-cycle duality에 의해 $G$ 에서 minimum cut을 찾는 것은 $G^*$ 에서 minimum cycle을 찾는 것과 동일하다. 아이디어는, $G^*$ 에서 적당한 사이클 $C$를 찾은 다음, $C$의 *안* 과 *밖* 에 대해서 분할 정복을 하고, 이후 $C$의 안과 밖을 오가는 사이클을 찾는 것이다. 분할 정복이 성립하려면 일단 $C$가 $G^*$ 의 Face들을 공평하게 쪼개야 할 것이다. 이런 $C$는 $O(n)$ 시간에 찾을 수 있다. $G^*$ 의 모든 Face를 대각선에 $\infty$ 가중치 간선 넣고 대충 triangulate하자. 다음, $G^*$ 에서 아무 정점을 잡고, sho..

대충 이 노트 의 끝자락에서 한 얘기를 정리했다. 그래프가 2-edge-connected 라고 가정하자. (그렇지 않다고 하더라도 코드가 크게 바뀌지 않는다) 알고리즘은 재귀적이다. 그래프 $G$ 의 DFS 트리에 대해서, 특정 서브트리의 노드를 모두 3-connected-component로 바꿔주는 알고리즘이 존재하고, 이 알고리즘을 bottom-up 으로 호출하면서 "서브트리의 답을 합쳐주면" 된다. 2-connected 인 경우를 예시로 생각해 보자. 서브트리를 컴포넌트로 분할하는 알고리즘이 있다면, bottom-up 알고리즘은 절선으로 연결되어 있지 않으며 루트를 포함하는 컴포넌트들을 가져온 후 이들을 합쳐주면 된다. 3-connected 의 경우에는 컴포넌트 하나만 가져올 수는 없으나, 대신 D..

https://arxiv.org/pdf/2211.09606.pdf 생각보다 내용이 많이 쉬워서 살짝 날먹이라고도 생각했다. 일단 핵심 내용은 다음과 같은 알고리즘의 존재성이다: $s, t$ flow가 $T$ 이하일때까지 $s, t$ flow를 incremental하게 관리하는 $O(Tm)$ 알고리즘이 존재한다. 일단 이 알고리즘에 대해서 논의하기 전에, 이러한 알고리즘이 존재하면 어떻게 전체 문제를 해결할 수 있는지 살펴보자. 플로우의 값이 $T$ 이하일 때까지는 $O(Tm)$ 알고리즘을 돌린다. 플로우의 값이 $T$ 를 넘어갔을 때는, 일단 플로우의 값이 $T$ 라고 하고 계속 간선 삽입 쿼리를 받자. 플로우의 값이 $T (1 + \epsilon)$ 을 넘어가면 위 값이 틀리게 된다. 이것이 일어나려면..