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|