• No products in the cart.






Created by:

Profile Photo

Last updated:

October 29, 2022


Unlimited Duration


This course includes:

Unlimited Duration

Badge on Completion

Certificate of completion

Unlimited Duration


15.082J/6.855J/ESD.78J is a graduate subject in the theory and practice of network flows and its extensions.

Network flow problems form a subclass of linear programming problems with applications to transportation, logistics, manufacturing, computer science, project management, and finance, as well as a number of other domains. This subject will survey some of the applications of network flows and focus on key special cases of network flow problems including the following: the shortest path problem, the maximum flow problem, the minimum cost flow problem, and the multi-commodity flow problem. We will also consider other extensions of network flow problems.

Course Curriculum

  • Introduction to network models Unlimited
  • Computational complexity and data structures Unlimited
  • Graph search algorithms Unlimited
  • Transformations and flow decomposition Unlimited
  • Shortest paths: label setting algorithms Unlimited
  • The radix heap algorithm Unlimited
  • Shortest paths: label correcting algorithms Unlimited
  • Algorithm analysis Unlimited
  • Basic algorithms for the maximum flow problem Unlimited
  • Combinatorial applications of maximum flows Unlimited
  • Preflow push algorithms Unlimited
  • More on preflow push algorithms Unlimited
  • Minimum cost flow: basic algorithms Unlimited
  • Minimum cost flow: polynomial time algorithms Unlimited
  • Applications of network flows; Linear programming review Unlimited
  • The network simplex algorithm Unlimited
  • Lagrangian relaxation 1 Unlimited
  • Lagrangian relaxation 2 Unlimited
  • Multicommodity flows 1 Unlimited
  • Multicommodity flows 2 Unlimited

About the instructor


Instructor Rating







Profile Photo
Massachusetts Institute of Technology
Copyright © 2022 OpenCoursa, All Rights Reserved