Advanced Flow Theory
The network problems multi-terminal flow, minimum cost flow, and multicommodity flow are fundamental to network design and performance evaluation. The first two can be solved exactly by the Gomory-Hu and the out-of-kilter algorithms, respectively. The former is a combinatorial algorithm on graph cuts, and the latter a primal-dual method. Multi-commodity flow is NP-complete for integer flows, and even for real-valued flows it is rather complex. Even if it in principle can be solved by linear programming, the number of constraints grow very fast with the problem size. An approximate method is therefore presented, which is suitable also for large problem instances.
Minimum cost ...