CMPUT 672: Algorithmic Graph Theory

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]