Increasing the Capacity of a Network: The Parametric Budget Problem

The problem considered in this paper is that of allocating a budget of resources among the links of a network for the purpose of increasing its flow capacity relative to given sources and sinks.

On the assumption that the cost of increasing each link capacity is linear, a labeling algorithm is described that permits rapid calculation of optimal allocations for all budgets.