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:

http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/download.html


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.