This course is of interest to students wanting to deepen their understanding of graph and network optimization problems.

Prerequisites:  COMP 3600 or the former COMP 3719

Availability: ⚠ This course is not planned to be offered in the near future.

Course Objectives

To give students efficient algorithms for solving some graph and network optimization problems and to provide them with techniques to show the apparent intractability of others.

Representative Workload

• Assignments 40%
• In-class Exam 25%
• Final Exam 35%

Representative Course Outline

• Graph theory fundamentals
• Algorithms on graphs:
• Graph connectivity and traversals
• Matching
• Shortest path
• Isomorphism
• Testing membership on families of graphs:
• Bipartite
• Planar
• Of bounded tree-width
• Some NP-complete and hard problems on graphs
• Colourability
• Independent sets
• Vertex cover
• Clique
• Approximation algorithms for some graph theoretic problems
• Resource scheduling problems
• Greedy algorithms and scheduling problems
• Dynamic programming algorithm for scheduling of weighted intervals
• The maximum flow problem and the Ford-Fulkerson algorithm
• Maximum flow and minimum cuts,
• The preflow-push maximum-flow algorithm
• Applications of network flow

Page last updated May 24th 2021