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.
Concentration: Operations Research
Academic Year: 2019-2020
Semester(s): Mini 2