Chapter 3

Advanced Flow Theory

Abstract

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.

Keywords

Multiterminal flow

Minimum cost ...

Get Design of Modern Communication Networks now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.