Abstract
In network problems such as the maximum-flow problem and the minimum-route problem, it is often desirable to attempt to simplify the given network before applying the various algorithms available for its solution. This is especially true when the maximum flow (or minimum route) between a number of different pairs of points is desired. Various transformations are discussed that can lead to considerable simplification. In particular, it is shown that wye-delta transformations analogous to those used with electrical networks are available. The application of these transformations to the maximum-flow problem (both with and without node capacities) is discussed and it is shown that for the minimum-route problem dual transformations apply. The effect of the topological properties of a network on the usefulness of these transformations is examined briefly. The application of the transformations to two networks in the literature is shown.