Course Page

Networks and Matchings

Course Number:

47836


Faculty

Egon Balas, eb17@andrew.cmu.edu


Program

PHD


Concentrations

Operations Research or Statistics


Course Description

This is the second part of a full semester course on algorithmic graph theory. It covers network flows and matchings, the two most important classes of polynomially solvable combinatorial optimization problems. Network flow models. Maximum flow, minimum cut. Minimum-cost flow. Connection with linear programming. Networks with gains. Matching in bipartite graphs. Non-bipartite matching. The Chinese postman problem.

Format

Lecture: 100min/wk and Recitation: 50min/wk


Pre-requisites

None