구사과

대충 이 노트 의 끝자락에서 한 얘기를 정리했다. 그래프가 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)$ 을 넘어가면 위 값이 틀리게 된다. 이것이 일어나려면..

Min-plus convolution 두 수열 $A = [a_0, a_1, ..., a_n]$, $B = [b_0, b_1,..., b_m]$ 이 있을 때 $c_k = \min_{k = i + j}(a_i + b_j)$ 를 구하는 것을 min-plus convolution이라고 한다. 저걸 $\max$ 로 바꾸면 max-plus convolution이다. min plus convolution은 3sum이나 apsp에서 오는 reduction은 없지만, 아직 subquadratic algorithm이 알려지지는 않은 상태 (cite: https://browse.arxiv.org/pdf/1702.07669.pdf). 수열이 convex하다는 것을, $a_{i+1} - a_i$ 가 단조증가 한다는 것으로 정의..