Multi-Commodity Network Flows

Abstract

A network is a set of nodes N ı connected by arcs with nonnegative arc capacities b ıj which indicates the maximum amount of flow that can pass through the arc from N ı to N j . Given all b ıj , there is a maximum flow from N ı to N j using all arcs. Under the assumption that b ıj = b jı , the present paper generalizes the max-flow min-cut theorem of Ford and Fulkerson to the problem of finding the maximum simultaneous flows of two commodities and gives an algorithm similar to the labelling method for constructing the two flows.