ABSTRACT
The network flow problem is an example of a theoretical subject that has many important applications. It also has generated algorithmic questions that have been in a state of extremely rapid development in the past 20 years. Altogether, the fastest algorithms that are now known for the problem are much faster, and some are much simpler, than the ones that were in use a short time ago, but it is still unclear how close to the ‘ultimate’ algorithm we are. The first algorithm for the network flow problem was given by Ford and Fulkerson. They used that algorithm not only to solve instances of the problem, but also to prove theorems about network flow, a particularly happy combination. The Ford-Fulkerson algorithm terminates when no flow augmenting paths exist. The chapter proves that when that happens, the flow will be at the maximum possible value, i.e., we will have found the solution of the network flow problem.
