Week | Topic | Student paper | Notes/exercises |
Jan 31 - Feb 3 | Planar graphs: duality, separators, the Monge property, shortest paths, reduced cost functions | 1 (Magnus Gausdal Find) | Week 1 |
Feb 7 - Feb 10 | Planar graphs: distance query algorithms, distance oracles, r-divisions | 2 (Philip Thyssen, Artavazd Hakhverdyan, Michael Franz) | Week 2 |
Feb 14 - Feb 17 | Planar graphs: min cut and max flow, duality of cuts/cycles, Hassin's algorithm (connection between max flow and shortest paths), Reif's algorithm | 3 (Christian Kudahl, Isabel Quintero, Rojin Kianian) | Week 3 |
Feb 21 - Feb 24 | General graphs: distance oracles | 4 (Magnus Gausdal Find) | Week 4 |
Feb 28 - Mar 2 | General graphs: multiplicative spanners (greedy spanner and the Thorup-Zwick and Baswana-Sen spanners), (α,β)-spanners, girth conjecture and its relation to spanners | 5 (Thomas Nørbo Jensen, Anders Knudsen, Jan Christensen) | Week 5 |
Mar 6 - Mar 9 | General graphs: additive spanners, dynamic connectivity | 6 (Bo Wiuff Lindhøj, Jakob Schou Rodenberg, Karim Sakatni Ljung) | Week 6 |
Mar 13 - Mar 16 | Time reserved for project | None | None |
J. Fakcharoenphol and S. Rao. Planar graphs, negative weight edges, shortest paths, and near linear time. Journal of Computer and System Sciences 72 (2006), 868-889.
G. F. Italiano, Y. Nussbaum, P. Sankowski, and C. Wulff-Nilsen. Improved Algorithms for Min Cut and Max Flow in Undirected Planar Graphs. Proc. 43rd ACM Symposium on Theory of Computing (STOC), San Jose, 2011.
C. Wulff-Nilsen. Approximate Distance Oracles with Improved Preprocessing Time. Proc. Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Kyoto, 2012, pp. 202-208.
S. Baswana and S. Sen. A Simple Linear Time Algorithm for Computing a (2k-1)-Spanner of O(n^{1+1/k}) Size in Weighted Graphs. ICALP 2003, LNCS 2719, pp. 384-396, 2003.
S. Baswana, T. Kavitha, K. Mehlhorn, and S. Pettie. New Constructions of (α,β)-Spanners and Purely Additive Spanners. Proc. sixteenth annual ACM-SIAM symposium on Discrete algorithms (SODA), pp. 672-681, 2005.
H. N. Djidjev. Efficient Algorithms for Shortest Path Queries in Planar Digraphs. Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, 1997, Volume 1197/1997, pp. 151-165.
R. Hassin. Maximum Flow in (s,t) Planar Networks. Information Processing Letters, Vol. 13, No. 3, pp. 107, 1981.
P. N. Klein, S. Mozes, and O. Weimann. Shortest Paths in Directed Planar Graphs with Negative Lengths: a Linear-Space O(nlog^{2}n)-Time Algorithm. Proc. 19th Ann. ACM-SIAM Symp. Discrete Algorithms, pp. 236-245, 2009.
M. Thorup and U. Zwick. Approximate distance oracles. Proc. thirty-third annual ACM Symposium on Theory of Computing (STOC), 2001, pp. 183-192.