Computing Science 419   Graph Algorithms   Winter Term 2001

assignments   outline   notes

MWF 9:00-9:50 CMP B41   Instructor: Ryan Hayward

Prerequisites: CS304 or the permission of the instructor.

Purpose: to introduce students to a wide variety of the most commonly used and studied graph algorithms.

Grading: term work 35%    midterm 15%    quizzes 15%    final 35%

Tentative Course Outline:

  • Basic graph concepts, definitions, and properties
  • Basic algorithmic and data structure concepts
  • Basic analysis concepts
  • Basic complexity concepts
  • algorithms: trees and distance
  • algorithms: matchings
  • algorithms: connectivity and network flow
  • algorithms: colouring
  • algorithms: cycles
  • algorithms: planarity
  • algorithms: perfect graphs

    References [the text by McHugh is required; copies are in the bookstore]

    M. Atallah
    Algorithms and Theory of Computation Handbook, M. Atallah (ed.), CRC Press, 1999, ISBN 0-8493-2649-4
    G. Chartrand & O. Oellermann
    Applied and Algorithmic Graph Theory, McGraw Hill, 1993, ISBN 0-07-557101-3
    A. Gibbons
    Algorithmic Graph Theory, Cambridge University Press, 1985, ISBN 0-521-28881-9 ..... [somewhat dated; out of print?]
    M.C. Golumbic
    Algorithmic Graph Theory and Perfect Graphs, Academic Press, 1980, ISBN 0-12-289260-7 ..... [specialized research primer, out of print?]
    J.A. McHugh
    Algorithmic Graph Theory, Prentice Hall, 1990, ISBN 0-13-023615-2 [out of print]
    D. West
    Introduction to Graph Theory, Prentice Hall, 1996, ISBN 0-13-227828-6 ..... [grad level, not algorithmic]
    R. Wilson
    Introduction to Graph Theory, 4th ed. Longman, 1996, ISBN 0-582-24993-7 ..... [inexpensive graph theory primer]

  • Questions? Send email to hayward@cs.ualberta.ca