- 10/2 2010: Hand-in assignment posted
- 23/1 2010: Literature list added
- 13/1 2010: Webpage created

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.

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

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

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 |

- [ALZ07] L. Allulli, P. Lichodzijewski,
and
N. Zeh. A faster cache-oblivious shortest-path
algorithm for undirected graphs with bounded edge
lengths. In
*Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms*, pages 910–919, 2007. - [Arg03]
L. Arge. The buffer tree: A technique for designing
batched external data structures.
*Algorithmica*37(1):1–24 (2003). - [ABD+07] L. Arge, M.A. Bender,
E.D. Demaine, B. Holland-Minkley, and
J.I. Munro. An optimal cache-oblivious priority queue
and its application to graph algorithms.
*SIAM Journal on Computing*36(6):1672–1695 (2007). - [ABT04] L. Arge, G.S. Brodal, and
L. Toma. On external-memory MST, SSSP and multi-way
planar graph separation.
*Journal of Algorithms*53(2):186–206 (2004). - [AGNS08] L. Arge, M.T. Goodrich,
M. Nelson, and N. Sitchinava.
Fundamental parallel algorithms for
private-cache chip multiprocessors. In
*Proceedings of the 20th ACM Symposium on Parallelism in Algorithms and Architectures*, pages 197–206, 2008. - [AGS10] L. Arge, M.T. Goodrich, and
N. Sitchinava.
Parallel external memory graph
algorithms. In
*Proceedings of the 24th IEEE International Parallel and Distributed Processing Symposium*, 2010. To appear. - [AMTZ03] L. Arge, U. Meyer, L. Toma,
and
N. Zeh. On external-memory planar depth-first
search.
*Journal of Graph Algorithms and Applications*7(2):105–129 (2003). - [AT04] L. Arge and
L. Toma. Simplified external memory algorithms for
planar DAGs. In
*Proceedings of the 9th Scandinavian Workshop on Algorithm Theory*, volume 3111 of*Lecture Notes in Computer Science*, pages 493–503. Springer-Verlag, 2004. - [AZ03] L. Arge and N. Zeh.
I/O-efficient strong connectivity and
depth-first search for directed planar graphs.
In
*Proceedings of the 44th IEEE Symposium on Foundations of Computer Science*, pages 261–270, 2003. - [BFMZ04] G.S. Brodal, R. Fagerberg,
U. Meyer, and
N. Zeh. Cache-oblivious data structures and
algorithms for undirected breadth-first search and shortest
paths. In
*Proceedings of the 9th Scandinavian Workshop on Algorithm Theory*, volume 3111 of*Lecture Notes in Computer Science*, pages 480–492. Springer-Verlag, 2004. - [BGVW00] A.L. Buchsbaum,
M.H. Goldwasser, S. Venkatasubramanian, and J. Westbrook.
On external memory graph traversal.
In
*Proceedings of the 11th ACM-SIAM Symposium on Discrete Algorithms*, pages 859–860, 2000. - [CGG+95] Y.-J. Chiang, M.T. Goodrich,
E.F. Grove, R. Tamassia, D.E. Vengroff, and J.S. Vitter.
External-memory graph algorithms.
In
*Proceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms*, pages 139–149, 1995. - [KKT95] D.R. Karger, P.N. Klein, and
R.E. Tarjan. A randomized linear-time algorithm to find
minimum spanning trees.
*Journal of the ACM*42(2):321–328 (1995). - [KS96] V. Kumar and E.J. Schwabe.
Improved algorithms and data structures for
solving graph problems in external memory.
In
*Proceedings of the 8th IEEE Symposium on Parallel and Distributed Processing*, pages 169–176, 1996. - [MZ08] A. Maheshwari and N. Zeh.
I/O-efficient planar
separators.
*SIAM Journal on Computing*38(3):767–801 (2008). - [MM02] K. Mehlhorn and U. Meyer.
External-memory breadth-first search with
sublinear I/O. In
*Proceedings of the 10th Annual European Symposium on Algorithms*, volume 2461 of*Lecture Notes in Computer Science*, pages 723–735. Springer-Verlag, 2002. - [MZ03] U. Meyer and N. Zeh.
I/O-efficient undirected shortest paths.
In
*Proceedings of the 11th Annual European Symposium on Algorithms*, volume 2832 of*Lecture Notes in Computer Science*, pages 434–445. Springer-Verlag, 2003. - [MR99] K. Munagala and A. Ranade.
I/O-complexity of graph algorithms.
In
*Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms*, pages 687–694, 1999. - [Vit08]
J.S. Vitter.
*Algorithms and Data Structures for External Memory*. now Publishers, Hanover, MA, 2008. - [Zeh02a]
N. Zeh.
*I/O-Efficient Algorithms for Shortest Path Related Problems*. PhD thesis, School of Computer Science, Carleton University, Ottawa, Canada, 2002. - [Zeh02b]
N. Zeh.
*I/O-Efficient Graph Algorithms*. Lecture notes of*EEF Summer School on Massive Data Sets*, 2002. - [STXXL] STXXL website.

3rd (Spring 2010)

5 ETCS points

English

Homework hand-in

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