Computer Science (CSC) Courses>Graph Algorithms

CSC422 - Graph Algorithms

Description

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.

Units

1.5

Hours: lecture-lab-tutorial

3-0-0

Prerequisites

  • Complete all of the following
    • Complete 1 of the following
      • Complete all of:
        • CSC226 - Algorithms and Data Structures II (1.5)
      • Complete all of:
        • CSC225 - Algorithms and Data Structures I (1.5)
        • MATH222 - Discrete and Combinatorial Mathematics (1.5)
    • minimum third-year standing.

Course offered by

Department of Computer Science

Course schedules

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

Use the buttons below to search the timetable. If the search results show 0 classes and the message ‘Please search again’, then the class is not scheduled for the selected term.