PhD Course on I/O-Efficient Graph Algorithms (Spring 2010, Q3)
Messages
- 10/2 2010: Hand-in assignment posted
- 23/1 2010: Literature list added
- 13/1 2010: Webpage created
Objectives
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.
Contents
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).
Lecturers
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
| 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
Download
Literature
- [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.
Quarter
3rd (Spring 2010)
Credits
5 ETCS points
Prerequisites
Course language
English
Compulsory programme
Homework hand-in
Evaluation
Based on mandatory hand-in and attendance, pass/fail