COMP 560
Graph Algorithms and Applications

Fall 2006-07
Prof. Whitesides

Approximate Course Contents

The text is Introduction to Graph Theory, by Douglas West. This is available in the Book Store. A reference is Graph Theory, by Reinhard Diestel. This is available free from Diestel's website:

For background reading on graph algorithms, the textbook for COMP 360, Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 2nd edition, is recommended. This book is on reserve in the Schulich Library and is henceforth referred to as CLRS. Particular topics to review are:

- ch. 22.1 on representations of graphs: 527-530;

- ch. 22.1 on Breadth First Search (BFS): pp. 531-538;

- ch. 22.3 on Depth First Search (DFS): pp. 540-547.

This material can also be found in the previous edition of the book, by Cormen, Leiserson, and Rivest (the ``white book''), but the chapter and page numbers are different.

Approximate Schedule (by lecture number)

1. Overview: mathematical beginnings, algorithmic beginnings, modern developments, and modern applications. Getting started: graph models, vertex degree

2. Paths and cycles: Hamilton cycles, Euler cycles, and some applications

3-4. Connectivity, applications of DFS

5-6. Trees, trees as models

7-8. Matchings and applications supplemental reading: CLRS 26.1-2, pp. 644-649

9. Problem session/review session

10. Midterm exam on Thursday, October 5 (possibly in the evening)

** No class on Tues. October 10 (follow a Monday schedule)

11-12. Network Flows

13-14. Planarity and Graph Layout

16. Colouring

17. Chordal Graphs

18. Path and Tree Decompositions

19. Fixed Parameter Tractable Algorithms for Colouring

20-21. Special topics

22-24. Student presentations

The midterm will be approximately Thurs. October 5, possibly in the evening. The last class meets Tuesday, November 28.

Special topics (either for lecture or student presentations):

Introduction to perfect graphs and the perfect graph theorem

Spectral graph theory, eigenvalues and eigenvectors, the Laplacian, and applications: spectral clustering methods

Application: Expanders in communication networks

Szemeredi's Regularity Lemma

Ramsey Theory

Random Graphs

World Wide Web graphs

back to COMP 560 home page.