Optimization in Graphs and Networks

3 credits

Basic graph theory, emphasizing trees, tree growing algorithms, and proof techniques. Problems chosen from: shortest paths, maximum flows, minimum cost flows, matchings, graph colouring. Linear programming duality will be an important tool. [3-0-0] Prerequisite: MATH 340.