PhD Course on I/O-Efficient Graph Algorithms (Spring 2010, Q3)



After attending this course, the participants will be familiar with the state of the art of graph algorithms in memory hierarchy models and will have an overview of research directions to pursue in this area.

Learning outcomes and competences

After attending this course, participants should be able to design I/O-efficient graph algorithms using the currently known techniques and analyze their I/O complexity.


This course focuses on the state of the art in techniques for designing I/O-efficient graph algorithms. Several memory hierarchy models are considered: I/O model, cache-oblivious model, and private-cache multicore model. The techniques range from techniques to solve elementary problems such as labelling trees to advanced techniques for solving shortest-path-type problems in undirected graphs and computing planar separators.

Participants are expected to have a basic background in I/O-efficient algorithm or to be willing to acquire it on their own. The assumed background is fairly minimal: I/O-efficient sorting, scanning, and priority queues are enough. This material will be reviewed very briefly at the beginning of the first class, but will not be discussed in detail.

The course will be held in an informal lecture style, meaning that the lecturers have an interactive teaching style that involves the students in discussion and that students are strongly encouraged to initiate discussions themselves, in order to clarify questions they may have.

The evaluation will be based on a set of theoretical exercises. The list of questions will be handed out at the latest during the second lecture, and answers are to be submitted by email at the end of the course. The grading is a simple PASS or FAIL.

Detailed list of topics is available in the course plan below (subject to adjustments as we go along).


Norbert Zeh (Dalhousie University), Nodari Sitchinava (MADALGO), and Deepak Ajwani (MADALGO).

Time and Place

A first meeting for planning the schedule of the course will be held Monday January 25, 2010, 14.15-15.00, in Turing 014.

Course plan

Week Date Content Literature Lecturer
4   Time-forward processing + greedy graph algorithms, List ranking, Euler tour and tree labelling [Arg03, CGG+95, Vit08, Zeh02a (Chapter 6), Zeh02b] Norbert Zeh
5   Several algorithms for minimum spanning trees (and connected components) [ABT04, CGG+95, KKT95, Zeh02b]
6   Breadth-first search, depth-first search, and shortest paths [BGVW00, KS96, MM02, MZ03, MR99, Zeh02b]
7   Cache-oblivious graph algorithms (minimum spanning tree, BFS, shortest paths) [ALZ07, ABD+07, BFMZ04]
8   Planar graphs (planar separators and their use to obtain optimal algorithms for planar graphs) [ABT04, AMTZ03, AT04, AZ03, MZ08, Zeh02b]
9   Engineering of I/O-efficient graph algorithms (Clever ideas beyond theory) Publications and projects on [STXXL] Deepak Ajwani
10   Graph algorithms for private-cache multicore architectures [AGNS08, AGS10, CGG+95] Nodari Sitchinava

Hand-in exercise




3rd (Spring 2010)


5 ETCS points


Course language


Compulsory programme

Homework hand-in


Based on mandatory hand-in and attendance, pass/fail