Feasibility of Two Commodity Network Flows

Abstract

The paper considers the problem of feasibility of integer flows in a two commodity network with integral capacities. The main result of the paper establishes conditions under which, in an Euler network, and for two non-negative integers a and b, there exists a two commodity flow, where the flow of the first commodity is of size a and the second flow of size b. This result is used to find some conditions for the case where a and b are not necessarily even.