CSC 422

Graph Algorithms

Units: 1.5, Hours: 3-0

Detailed study, from the algorithmic point of view, of some tractable and intractable graph problems. Tractable problems covered include: path problems, spanning trees, network flows, matchings, planarity testing.

The theory of NP completeness is reviewed and applied to graph problems which are apparently intractable, e.g., the clique, independent set, vertex cover, Hamiltonian circuit, Travelling Salesman and colouring problems. Approximation and probabilistic solutions to the intractable problems are discussed.

Models of randomized and parallel computation and their associated complexity classes are outlined and examples of these kinds of algorithms for some graph problems are examined.

Note: Credit will be granted for only one of 422 and a topics course with similar content.

Prerequisites: A minimum grade of B+ in 225, a minimum grade of B+ in MATH 222 and third- or fourth-year standing.

Undergraduate course in Computer Science offered by the Department of Computer Science in the Faculty of Engineering.