구사과

정말 갑작스럽지만, 저번 주 3주 전 6주 전 (...) 암트랙의 Empire Builder를 타본 후기를 써 보려고 한다. 3월 6일 ~ 3월 8일은 공휴일이 끼어 있는 주도 아니고 아무 일도 없는 시기지만, 과제가 없길래 2주 전쯤에 충동적으로 티켓을 구매했다. 보스턴 → 시애틀 비행기, Empire Builder, 시카고 호텔 1박, 시카고 → 보스턴 비행기 표를 끊고, 평소처럼 살다가 전날 최소한의 준비물만 챙겨 출발했다. Day 1 Seattle 4시 반 기상 후 Boston Logan에서 6시 50분 비행기를 타고 시애틀로 갔다. 비행 시간은 약 6시간 정도로, 시차 때문에 3시간이 당겨져서 도착 시간은 10시였다. 몇천 km를 넘어서 Pacific에 왔다는 실감은 그다지 들지 않았다. 날씨가..

Undirected graph $G = (V, E)$ 에 대해, $G$의 $t$-spanner $H = Spanner(G,t) = (V, E^\prime)$ 는 다음 성질을 만족한다: $E^\prime \subseteq E$ 모든 $u, v \in V$ 에 대해, $dist(H, u, v) \le dist(G, u, v) \times t$ $E^\prime$ 의 크기가 작음 즉, 최단 경로를 Approximate하게 보존하는 Sparsification이다. Equivalent하게, 다음과 같이 표현할 수도 있다. $E^\prime \subseteq E$ 모든 $(u, v) \in E$ 에 대해, $dist(H, u, v) \le dist(G, u, v) \times t$ $E^\prime$ 의 크기가 작..

Even-Shiloach Algorithm은 Unweighted directed graph $G = (V, E)$ 에 대해서 incremental / decremental SSSP를 빠르게 해결하는 알고리즘이다. Naive하게는 매번 BFS를 해서 $O(m^2)$ 시간에 해결할 수 있는데, 이 알고리즘을 사용하면 이를 $O(nm)$ 으로 최적화할 수 있다. $O(m^2)$ 에 비해서 엄청나게 효율적이진 않지만 분명히 nontrivial한 bound이고, 내가 아는 state-of-the-art method는 전부 다 Near-linear가 아니라 $O(nm)$ 에 훨씬 가까운 바운드이다. 그것도 복잡한 알고리즘들이 대다수. 이 글에서는 원래 Even-Shiloach Algorithm보다 강한 statem..