Incremental Minimum Flow Algorithms

Abstract

There are various situations in which real-world problems can be modeled and solved as minimum flow problems. Sometimes, in these situations, minor data changes may occur, leading to corresponding changes of the networks in which the practical problems are modeled as flow problems, such as slight variations in capacity or lower bound. For instance, the capacity or the lower bound of an arc may increase or decrease in time, leaving one with no other choice than finding the new minimum network flow. Given both the various ways in which the networks can be changed and the high frequency of these changes, it is desirable to find as fast a computation method for minimum flow as possible. This paper is focused on the cases that concern increasing and decreasing the capacity or the lower bound of an arc. For these cases, both the minimum flow algorithms and the dynamic minimum flow algorithms that are already known are inefficient. Our incremental algorithms for determining minimum flow in the modified network are more efficient than both the above-mentioned types of algorithms. The proposed method starts from the initial network minimum flow and solves the minimum flow problem in a significantly faster way than recalculating the new network minimum flow starting from scratch.

Keywords

• network flows
• combinatorial optimization
• minimum flow
• incremental algorithms
• decreasing path algorithms