Efficient Graph Algorithms

Lecturer: Christian Wulff-Nilsen

Evaluering/handlingsplan:

Can be downloaded here and here.

Plan:

We meet in room U62 on Tuesdays 14.15-16.00 and in the IMADA seminar room on Wednesdays 10.15-12.00 and Fridays 12.15-14.00. In general, lectures by me will be given on Tuesdays, exercise sessions on Wednesdays, and student presentations on Fridays. Notes and exercises for each week will be handed out on Tuesdays and uploaded to this page shortly thereafter. The following plan is subject to change.

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

Project:

The project consists of two parts. Part I can be found here and part II here. Deadline for handing in the project is March 30, 2012 at 13:00.

Credit:

A credit of 5 ECTS is obtained by

Papers for student presentations:

This is the list of papers that may be chosen for your group's presentation (paper 1 is reserved for Magnus). Each group chooses one paper. Papers are handed out during class and you can also get them (and the project) at the library.

  1. P. N. Klein, S. Mozes, and O. Weimann. Shortest Paths in Directed Planar Graphs with Negative Lengths: A Linear-Space O(nlog2n)-Time Algorithm. ACM Transactions on Algorithms, Vol. 6, No. 2, Article 30, 2010.
  2. 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.

  3. 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.

  4. 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.

  5. S. Baswana and S. Sen. A Simple Linear Time Algorithm for Computing a (2k-1)-Spanner of O(n1+1/k) Size in Weighted Graphs. ICALP 2003, LNCS 2719, pp. 384-396, 2003.

  6. 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.

Additional papers used in the course:

  1. 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.

  2. R. Hassin. Maximum Flow in (s,t) Planar Networks. Information Processing Letters, Vol. 13, No. 3, pp. 107, 1981.

  3. P. N. Klein, S. Mozes, and O. Weimann. Shortest Paths in Directed Planar Graphs with Negative Lengths: a Linear-Space O(nlog2n)-Time Algorithm. Proc. 19th Ann. ACM-SIAM Symp. Discrete Algorithms, pp. 236-245, 2009.

  4. M. Thorup and U. Zwick. Approximate distance oracles. Proc. thirty-third annual ACM Symposium on Theory of Computing (STOC), 2001, pp. 183-192.