A polynomial time algorithm for the maximal constrained network flow problem based on the bit-arc capacity scaling technique

Abstract

An efficient polynomial time algorithm for solving maximum flow problems in directed networks has been proposed in this paper. The algorithm is basically based on successive divisions of capacities by multiples of two; it solves the maximum flow problem as a sequence of O(m) shortest path problems on residual networks with n nodes and m arcs. It runs in O(m2 r) time, where r is the smallest integer greater than or equal to log B, and B is the largest arc capacity of the network. A numerical example has been illustrated using this proposed algorithm.

Keywords

• maximum flow problem
• bit-capacity scaling algorithm
• polynomial time algorithm
• augmenting path method
• network flow