Increasing the Capacity of a Network: The Parametric Budget Problem - Fulkerson, D. R. (Management Science, 1959)
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.