On feasibility conditions of multicommodity flows in networks

Abstract
An alternate derivation of the dual condition (called the severance-value condition in this paper) to feasibility of the multicommodity flow problem is given by graph theoretical arguments. That is, a multicommodity flow of given requirements is feasible if and only if the capacity of every severance is no less than its least capacity consumption for the flow. A severance is a set of the edges with nonnegative integer coefficients. Even when the severance-value condition is satisfied by a certain finite subset of severances, the multicommodity flow is shown to be still feasible if each requirement is allowed to be reduced by an appropriate amount\mu. This truncation allowance\muis estimated in terms of the network topology and the capacity function.

This publication has 0 references indexed in Scilit: