A polynomial time algorithm for the maximal constrained network flow problem based on the bit-arc capacity scaling technique
2023
Muhammad Tlas
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.
Show more [+] Less [-]Bibliographic information
This bibliographic record has been provided by Directory of Open Access Journals
