Networking

Incremental Algorithms for Optimal Flows in Networks

Date Added: Feb 2012
Format: PDF

In this paper, the authors will use incremental algorithms in order to save computational time when solving different network flow problems. They will focus on two important network flow problems: maximum flow problem and minimum cost flow problem. Incremental algorithms are appropriated to be used when they have a network in which they already have established an optimal flow (in their case either a maximum flow or a minimum cost flow), but they must modify the network by inserting a new arc or by deleting an existent arc. An incremental algorithm starts with an optimal flow in the initial network and determines an optimal flow in the modified network.