On Multi-Commodity Maximal Dynamic Flows

Ford and Fulkerson have shown that a single-commodity maximal dynamic flow can be obtained by solving a transshipment problem associated with the static network and thereby finding the maximal temporally repeated dynamic flow. This flow is known to be an optimal dynamic flow. However, this result cannot be extended to the multi-commodity maximal dynamic flow problem. This paper shows that, for sufficiently large number of time periods, the difference between the multi-commodity maximal dynamic flow and the temporally repeated multi-commodity flow is bounded by a constant. In addition, it calculates this bound.