Maximum flow in a network with an underestimated arc capacity

Abstract

There are problems arising in real life that can be modeled and solved as maximum flow problems in several networks, some of these differing only by an arc capacity. Suppose that we have previously determined a maximum flow in a network G, but we also need to find a maximum flow in a network having the same structure as G and the same arc capacities except one: the capacity of a given arc (k; l) which has increased by a given amount a. In this paper, we will show how a maximum flow in the new network can be obtained in O(am) time starting from the maximum flow in the initial network.