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. Some tractable problems are path problems, spanning trees, network flows, matchings, and planarity testing. Some intractable problems are clique, independent set, vertex cover, Hamiltonian cycle, and colouring problems. Various strategies for handling intractable problems are presented including intelligent backtracking, distributed and parallel computing, parameterized complexity, restrictions to graph sub-classes, randomized and approximation algorithms.

Prerequisites:

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

Schedules:
Summer Fall Spring

Note that not all courses are offered in every term. If a course is not offered, the schedule page will alert you that "No classes were found that meet your search criteria."