Carnegie Mellon University

Advanced Graph Theory

Course Number: 47836

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.

Degree: PhD
Concentration: Operations Research
Academic Year: 2019-2020
Semester(s): Mini 2
Required/Elective: Elective
Units: 6

Format

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