Design of Modern Communication Networks

Chapter 2

Networks and Flows

Abstract

For network topologies, graphs are natural models. Concepts from graph theory are used in many present-day network algorithms and are the foundation of most network design algorithms. More complex algorithms for network flows can often be decomposed as a sequence of simpler ones. Some of the most basic problems are network connectivity, shortest path, and maximum flow.

These problems can be solved by different methods. As a matter of fact, almost all network problems can be formulated as linear programs. However, as the complexity grows, there are often more efficient solution algorithms available. A number of alternative solution methods to linear programming, such as primal-dual methods, dynamic programming, ...