Home

Network Biology, 2022, 12(3): 81-96
[XML] [EndNote] [RefManager] [BibTex] [ Full PDF (785K)] [Comment/Review Article]

Article

Using the binary representation of arc capacity in a polynomial time algorithm for the constrained maximum flow problem in directed networks

Muhammad Tlas
Scientific Services Department, Atomic Energy Commission, P. O. Box 6091, Damascus, Syria

Received 25 April 2022;Accepted 30 May 2022;Published online 6 June 2022; Published 1 September 2022
IAEES

Abstract
In this paper, the binary representation of arc capacity has been used in developing an efficient polynomial time algorithm for the constrained maximum flow problem in directed networks. The algorithm is basically based on solving the maximum flow problem as a sequence of O(n2) shortest path problems on residual directed networks with n nodes generated during iterations. The complexity of the algorithm is estimated to be no more than O(n2mr) arithmetic operations, where m denotes the number of arcs in the network, and r is the smallest integer greater than or equal to log B (B denotes the largest arc capacity in the directed network). Generalization of the algorithm has been also performed in order to solve the maximum flow problem in a directed network subject to non-negative lower bound on the flow vector. A formulation of the simple transportation problem, as a maximal network flow problem has been also performed. Numerical example has been inserted to illustrate the use of the proposed algorithm.

Keywords maximum flow problem;scaling algorithm;polynomial time algorithm;augmenting path method;network flow.



International Academy of Ecology and Environmental Sciences. E-mail: office@iaees.org
Copyright © 2009-2024 International Academy of Ecology and Environmental Sciences. All rights reserved.
Web administrator: office@iaees.org, website@iaees.org; Last modified: 2024/3/29


Translate page to: