INPUT OUTPUT

**Problem:**
What is the maximum flow you can route from *s* to *t* while
respecting the capacity of each edge.

**Excerpt from**
The Algorithm Design Manual:
Applications of network flow go far beyond plumbing. Finding the most cost-effective way to ship goods between a
set of factories and a set of stores defines a network flow problem, as do resource-allocation problems in
communications networks and a variety of scheduling problems.

The real power of network flow is that a surprising variety of linear programming problems that arise in practice can be modeled as network flow problems, and that special-purpose network flow algorithms can solve such problems much faster than general-purpose linear programming methods. Several of the graph problems we have discussed in this book can be modeled as network flow, including bipartite matching, shortest path, and edge/vertex connectivity.

Network Coding Theory by R Yeung and S-Y. Li and N. Cai and Z. Zhang | Network Flows : Theory, Algorithms, and Applications by Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin | Introduction to Algorithms by T. Cormen and C. Leiserson and R. Rivest and C. Stein |

Flows in Networks by L. Ford and D. R. Fulkerson |

This page last modified on 2008-07-10 . www.algorist.com