By Therese Biedl
This document results from graduate courses that I taught at the University of Waterloo in Fall 1999, Winter 2002 and Winter 2004. Students were asked to take lecture notes in LATEX, which I then compiled and edited for this document.
The topic of graph algorithms is so unbelievably big that it is entirely hopeless to want to hold just one course about them. Even focusing on advanced graph algorithms (whatever "advanced" may mean) doesn't help, because there is still too many algorithms to cover.
The focus of this course was therefore even more specialized: I wanted to look at problems which are "normally" difficult (by which I mean a high polynomial running-time, or even NP-complete), but which can be solved faster when focusing on a specialized subclass. These notes assume that the reader is familiar with the following topics:
- Data structures, in particular lists, stacks, queues, trees, bucket sorting, graph traversals.
- Graph theory and combinatorial optimization, in particular graph definitions, shortest paths, °ows, matchings.
- Analysis of algorithms, in particular the O-notation and NP-completeness.
For some of these topics, a brief review is given here (see the appendix), but for more details, the reader is referred to for example [CLRS00] for data structures and analysis of algorithms, and [Gib85] for graph theory and combinatorial optimization.