-
Poly-logarithmic Randomized Bellman-Ford (2/2)
Introduction 지난 글에 이어 Bringmann 2023의 near-linear time shortest single source path (SSSP) 문제를 해결하는 부분을 더 다루어보도록 하겠습니다. 간선의 가중치가 $-W^{-}$ 이상인 weighted digraph에 대해 $\mathcal{O}(\log^{2} n \log(nW))$ 번의 dijkstra algorithm으로 shortest path tree, negative cycle 중 하나를 반환하는 문제입니다. 지난 글에서는 다음의 특수한 조건을 만족하는 Restricted SSSP (RSSSP)를 $\mathcal{O}(\log^{2} n)$ 번의 dijkstra algorithm으로 해결하는 Las-Vegas algorithm을 소개하였습니다. Definition. Directed graph $G$에 어떤 정점 $s \in V(G)$가 존재하여 다음을 만족하면 $G$를 restricted graph라고 한다....
-
Linear-Time Encodable Linear Code
Error-correcting code $[n, k, d]$ code: 길이 $k$인 message $m$을 길이 $n$인 codeword $Enc(m)$으로 인코딩하는 $Enc$에 대해, 서로 다른 두 message의 codeword의 hamming distance (서로 다른 entry의 개수)가 항상 $d$ 이상일 때 이를 $[n, k,d]$ code라 합니다. 이 때 가장 가까운 두 codeword가 서로 다른 비율을 나타내는 $\Delta = \frac{d}{n}$을 code의 relative distance라고 부릅니다. Example: Repitition code 예를 들어, “0101”을 “000111000111”로 encoding하는, 원래의 비트를 세 번씩 반복하는 repitition code의 경우 이는 $[3k, k, 3]$ 코드이고,...
-
Poly-logarithmic Randomized Bellman-Ford (1/2)
Introduction Single-Source Shortest Path (SSSP) 문제는 알고리즘 입문에서부터 다루는 아주 기초적이고, 또 중요한 문제입니다. 엄밀하게 적자면, $n$개의 정점과 $m$개의 가중치 있는 단방향 간선을 갖는 그래프 $G$와 시작 정점 $s$가 주어질 때, 모든 점 $i$에 대해 $s$에서 $i$로 가는 최단 경로의 길이 $\mathrm{dist}(s, i)$ 를 묻는 문제입니다. 일반적으로 가중치가 모두 양수인 경우에 사용할 수 있는 Dijkstra’s algorithm과 가중치의 값과 무관하게 사용할 수 있는 Bellman-Ford algorithm이 가장 유명합니다. 각각의 시간 복잡도는 $\mathcal{T}[\text{Dijkstra}]$: Practical한 선에서 $O(m \log n).$...
-
Minimum Cuts in Near-Linear Time
Introduction Weighted graph $G$에 대해, $G$의 min-cut 혹은 edge connectivity 는 $G$의 connected component가 둘 이상이 되도록 하기 위해 제거해야 하는 가중치 합으로 정의됩니다. 이름 그대로 네트워크를 단절시키기 위해 필요한 최소 비용으로, 수많은 파생과 응용이 가능합니다. 이 글에서는 $n$개의 정점, $m$개의 간선을 가진 weighted graph $G$의 min-cut을 near-linear time ($\tilde{O}(m)$)에 구하는 최초의 방법인 D. R. Karger의 Minimum Cuts in Near-Linear Time을 리뷰합니다. Definition 그래프 $G$는 non-negative weighted graph로 가정합니다. 즉, weight는 음 아닌 실수 값을...
-
Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms
Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms 그래프의 최소 컷 (Minimum cut) 은 그래프를 연결되지 않게 하기 위해서 지워야 하는 간선의 최소 개수, 혹은 간선 가중치의 최소 합이다. 만약 간선의 최소 개수로 컷을 정의한다면, 최소 컷은 그래프의 connectivity 를 정의하는 수량이 된다. 고로 최소 컷은 그래프가 주어졌을 때 계산하고 싶은 가장 기초적인 수량에 해당되며, 응용 예시 또한 무수히 많다. 그래프의 최소 컷을 계산하는 방법은 크게 3가지가 있다. 아래에 해당 방법의 발견 시간 순으로 나열한다. (아래...
-
그래프의 간선 색칠 문제
그래프의 간선 색칠 문제 그래프 $G$가 주어질 때, 각 정점 $v$에 대해 자연수 색상 을 배정하여 간선으로 직접 연결된 정점 쌍마다 다른 색상을 배정해야 한다. 이 때, 배정된 최대 색상을 최소화해보자. 즉, 서로 다른 색의 수를 최소화해야 한다. 이 문제는 그래프의 정점 색칠 (Graph Coloring, Vertex Coloring) 문제로, NP-complete임이 잘 알려져 있다. 너무 어려우니까 다른 문제를 생각해 보자. 그래프 $G$가 주어질 때, 각 간선 $v$에 대해 자연수 색상 을 배정하여 간선으로 직접 연결된 정점 쌍마다...