CMPUT 672     Algorithmic Graph Theory     Fall 2011

• http://www.cs.ualberta.ca/~stewart/c672/
  
  
• Time: TTh 11:00-12:20
• Place: ED N2 119 101
  
  
• Professor: Lorna Stewart, lorna.stewart@ualberta.ca, 304 Athabasca Hall
  
  
• Prerequisite: cmput 304 or equivalent
  
  
• The course will focus on mathematical proofs and algorithms in graph theory.
  On assignments/projects, students will solve problems, prove theorems, and design algorithms.


• Grading:
  • 2 assignments: 30
  • 2 presentations in class (topic to be assigned) with handouts: 30
  • project proposal: 5
  • project write-up and presentation: 35
  
  
• Books on graph classes (on reserve Sci and Tech library):
  • Brandstadt, Le, and Spinrad, Graph Classes: A Survey, SIAM, 1999
    
  • Golumbic, Algorithmic Graph Theory and Perfect Graphs, 1980, 2nd ed 2004
    
  • Spinrad, Efficient Graph Representations, 2003
  
  
• Graph theory references:
  • Bondy and Murty, Graph Theory, 2008 (available online through U of A Library)
  • Bondy and Murty, Graph Theory with Applications, 1976 (follow the Books link)
  • Reinhard Diestel, Graph Theory, 1997
  • West, Introduction to Graph Theory, 2nd ed, 2001 (on reserve Sci and Tech library)
  
  
• Algorithms and NP-completeness:
  • Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, 2nd ed, 2001 (available online through U of A Library)
  • Garey and Johnson, Computers and Intractability: A guide to the theory of NP-Completeness, 1979 (on reserve Sci and Tech library)
  
  
• Graph theory links
• Definitions/Notation Handout
  
• Notes on intersection graphs
  
  
• UA Resources for Students:
  • Centre for Writers
  • Academic Support Centre
  • Truth in Education
  • Don't Cheatsheet