AMS 546, Network Flows
Theory of flows in capacity-constrained networks. Topics include maximum flow, feasibility
criteria, scheduling problems, matching and covering problems, minimum-length paths,
minimum-cost flows, and associated combinatorial problems.
3 credits, ABCF grading
Text:
Network Flows, by Ahuja, Magnanti, and Orlin, 93, Prentice-Hall
ISBN#: 9780136175490 - Recommended
Spring 2020 Semester (all textbooks are recommended):
"Network Flows" by Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin, 1993, Prentice-Hall, ISBN: 9780136175490
"Introduction to Graph Theory" by Douglas B. West, 2001 (2nd edition), Prentice-Hall, ISBN: 0130144002
"Networked Life: 20 Questions and Answers" by Mung Chiang, 2012, Cambridge University Press, ISBN: 9781107024946
Learning Outcomes:
1) Understand fundamental graph theory of directed and undirected graphs:
* Basic definitions;
* Degree sequences.
2) Understand, analyze, and apply the methods of depth-first search and breadth-first
search:
* Connectivity, strong connectivity;
* 2-connected components;
* Period of a directed graph.
3) Understand algorithmic problems involving computing trees in networks:
* Minimum spanning trees;
* Steiner trees;
* Degree-constrained trees;
* Min-max paths.
4) Understand tour and cycle problems in networks:
* Euler tours;
* Hamilton cycles, including necessary conditions for existence, sufficient
conditions for existence;
* Chinese Postman problem;
* Traveling Salesperson Problem and variants.
5) Understand the basics of computational complexity theory:
* Problem reductions;
* NP-hardness, NP-completeness.
6) Understand, analyze and apply path optimization algorithms in networks:
* Shortest path problem;
* Algorithms, including Dijkstra, Bellman-Ford, Floyd-Warshall.
7) Understand the formulation, analysis, and algorithmic solution of maximum flow
problems in networks:
* Maximum flow formulation;
* Algorithms for maximum flow, including Ford and Fulkerson, polynomial-time
methods;
* Max flow/min cut theorem and its consequences;
* Integrality of linear programming solutions to maximum flow.
8) Understand the formulation, analysis, and algorithmic solution of minimum-cost
flow problems in networks:
* Formulations and applications;
* Optimality conditions;
* Algorithms, including cycle cancelling and successive shortest paths.
9) Understand the formulation, analysis, and algorithmic solution of matching problems
in networks:
* Bipartite and non-bipartite matching;
* Algorithms;
* Applications.
10) Understand the basics of graph coloring problems in planar and nonplanar graphs.
11) Understand the notion of a provable approximation algorithm and its role in solving hard optimization problems.