A Note on Parametric Network Flows

Abstract

In their paper [Doulliez, P. J., M. R. Rao. 1971. Maximal flow in a multi-terminal network with any one are subject to failure. Management Sci. 18 (1, September) 48–58.], Doulliez and Rao present algorithms that solve two flow problems for a single source, multi-terminal network. The first problem that they solve is the construction of a flow that maximizes the value of t , where the demand at each sink is a nondecreasing, linear function of t . Given such a flow, the second problem that they solve is the construction of a flow that maximizes the value of t when the capacity of an arc is reduced. This paper supplies a finiteness proof for the first algorithm and sketches a finiteness proof for the second algorithm. The proofs are based on the well-known fact that a network possesses only a finite number of different spanning trees.