Mathematics (MATH)
School of Mathematics and Statistics
Faculty of Science
MATH 3802 [0.5 credit]
Combinatorial Optimization
Dijkstra's algorithm and Bellman-Ford algorithm for the minimum weight dipath problem, the minimum weight spanning tree problem, augmenting path algorithm and preflow-push algorithm for the max-flow min-cut problem, connections to linear programming, matchings in bipartite graphs and the assignment problem, the transportation problem, and the general minimum-cost flow problem.
Prerequisite:
MATH 3801, or permission of the School.
Lectures three hours a week, tutorial one hour a week.