Capacity of a Network with Increasing Demands and Arcs Subject to Failure

This paper considers a multiple-sink network with demand at some nodes of the network being an increasing function of time. It gives, for source-sink planar networks, an algorithm for finding the maximum time up to which all demands can be satisfied. This algorithm is applicable even if any set of a specified number of arcs of the network has the arc capacities reduced to given lower values. The method presented is based upon the properties of the dual network. Finally, the paper works out a numerical example and discusses an application of the method to the optimal-capacity planning of a network.