Maximum Flow and Minimum Cost Flows

Suggested Readings

  • Cormen, Leiserson and Rivest, Introduction to Algorithms. Chapter 27 (Maximum Flow).
  • Goldberg's algorithm for maximum flow in perspective: a computational study. R. J. Anderson and J. C. Setubal. In Network Flows and Matching.
    This has some nice experimental results that compare several different maximum flow algorithms over a variety of graph types.

    • Secondary Topics

  • Modeling Traffic. See D. J. Zawack and G. L. Thompson. A dynamic space-time network flow model for city traffic congestion. (abstract).
  • Min-Cost Flow. See
  • An Efficient implementation of a scaling minimum-cost flow algorithm, Andrew V. Goldberg. STAN-CS-92-1439.
    This gives a brief description of the successive approximation push-relabel method of Goldberg and Tarjan (the state-of-the-art). What is more interesting, however, are the experimental results.

    • Other Readings

  • R. Ahuha, T. Magnanti and J. Orlin, Network flows: theory, algorithms, and applications Prentice Hall 1993.
  • Network Flows and Matching: First DIMACS Implementation Challenge, David Johnson and Catherine McGeoch (editors). AMS, 1993.

    • Useful Links

  • Network-flow codes and models (FTP directory).
  • Bibliography on Network Flow Problems

    • Note: The material on this page is taken from Algorithms in the "Real World"

    Back to the topic list.