CMPUT 672: Algorithmic Graph Theory

Fall Term 2006   T R 1100-1220   MEC 4-1

Instructor: Prof. Ryan Hayward

Office Hours: Athabasca 301 M1100-1200 W 1100-1200 F 1100-1200

Prerequisites:   a strong background in algorithms, theory of computation, and math

Course Outline: the story of Claude Berge and the Strong Perfect Graph Theorem

Course Objectives/Content: an introduction to algorithmic graph theory, emphasizing classes/algorithms/structures/compositions/problems related to Claude Berge and perfect graphs

Grading:*10% penalty/day late
50% quizzes (first absent quiz pro-rated; others score zero)   5% book report (Sept 28*)   15% project (proposal Oct 5, report Nov 30*)   10% presentation (Nov; to be scheduled)   20% exam (Nov 23) 

Final letter grade assignment: as per UofA Marking and Grading Guidelines, final grades will be assigned as a combination of the UofA illustrative sample 600 level graduate course distribution (A+ A A- B+ B B- C+ C C- D+ D F resp.% 15 15 15 17 16 10 7 2 1 0 1 1) together with absolute cutpoints reflecting the instructor's view of the UofA graduate course descriptors: A* excellent, B/B+ good, C+/B- satisfactory, F-C fail

Text:   none required; references below   reference typos   basic definitions

C. Berge
The Theory of Graphs, Dover [early text by Berge]
C. Berge
Who killed the Duke of Densmore?
in Oulipo Laboratory (Raymond Queneau ed.), Atlas Press 1996.
C. Berge and V. Chvatal, eds.
Topics on Perfect Graphs (Ann. Disc. Math. Vol. 21), Elsevier 1984 [research papers; out of print ?]
M.C. Golumbic
Algorithmic Graph Theory and Perfect Graphs, 1980, revised 2004
J. Ramirez-Alfonsin and B. Reed, eds.
Perfect Graphs, Wiley, 2001 [survey papers]
J. Spinrad
Efficient Graph Representations, Fields Inst. Mongraphs, 2003
D. West
Introduction to Graph Theory, Prentice Hall, 1996 [not algorithmic, 30 pages on perfect graphs]
R. Wilson
Introduction to Graph Theory, 4th ed. Longman, 1996 [graph theory primer]