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

 

Instructor's 546 Website

 

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.