CSC 522

Graph Algorithms

Units: 1.5

Hours: 3-0-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.

Graduate course in the Computer Science program offered by the Faculty of Graduate Studies.

Fall 2019 Spring 2020 Summer 2020

Summer timetable available: February 15. Fall and Spring timetables available: May 15.

Before these dates the class schedule will show "No classes were found that meet your search criteria". If this message is shown after these dates, the course is not scheduled for the selected term.