An incremental algorithm for the maximum flow problem

An incremental algorithm for the maximum flow problem

0.00 Avg rating0 Votes
Article ID: iaor20043281
Country: Netherlands
Volume: 2
Issue: 1
Start Page Number: 1
End Page Number: 17
Publication Date: Jan 2003
Journal: Journal of Mathematical Modelling and Algorithms
Authors: ,
Abstract:

An incremental algorithm may yield an enormous computational time saving to solve a network flow problem. It updates the solution to an instance of a problem for a unit change in the input. In this paper we have proposed an efficient incremental implementation of maximum flow problem after inserting an edge in the network G. The algorithm has the time complexity of O(([Delta]n)2m), where [Delta]n is the number of affected vertices and m is the number of edges in the network. We have also discussed the incremental algorithm for deletion of an edge in the network G.

Reviews

Required fields are marked *. Your email address will not be published.