Parametric Network Flows

This paper considers a directed capacitated network in which the supply at each source node and the demand at each sink node is a linear function of a parameter t. It presents two algorithms that determine the range of values for the parameter t; they correspond to the primal and dual linear-programming algorithms that solve this problem. The dual algorithm appears to have a simpler structure.