### 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]