Maximum Flow Problem

Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin

ABSTRACT

The maximum flow problem seeks the maximum possible flow in a capacitated network from a specified source node s to a specified sink node t without exceeding the capacity of any arc. A closely related problem is the minimum cut problem, which is to find a set of arcs with the smallest total capacity whose removal separates node s and node t. We described several applications of the maximum flow problem in Chapter 8.1. In this article, we describe algorithmic methods for solving these problems, beginning by considering a generic augmenting path algorithm for solving the maximum flow problem. A byproduct of this algorithm is the well-known max-flow min-cut theorem stating that the value of the maximum