Combinatorial Optimization

3 credits · Graduate

Various graph algorithms will be presented and analyzed. Specifically we will treat the algorithms for the problems: minimum spanning tree, shortest path, maximal flow, minimum cost flow, maximum matching. For each problem, various algorithms will be presented and compared. The link with Linear Programming, especially LP-Duality, will receive special attention. PREREQUISITES: Some knowledge of linear programming and the theory of algorithms is recommended. CROSSLISTED: MATH 4320.03