Using the binary representation of arc capacity in a polynomial time algorithm for the constrained maximum flow problem in directed networks
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 problem...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
International Academy of Ecology and Environmental Sciences
2022-09-01
|
| Series: | Network Biology |
| Subjects: | |
| Online Access: | http://www.iaees.org/publications/journals/nb/articles/2022-12(3)/constrained-maximum-flow-problem-in-directed-networks.pdf |
| _version_ | 1818495027196723200 |
|---|---|
| author | Muhammad Tlas |
| author_facet | Muhammad Tlas |
| author_sort | Muhammad Tlas |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-10T18:14:44Z |
| format | Article |
| id | doaj.art-e9584d2c62d34cb099fba3cfa11dc1e3 |
| institution | Directory Open Access Journal |
| issn | 2220-8879 |
| language | English |
| last_indexed | 2024-12-10T18:14:44Z |
| publishDate | 2022-09-01 |
| publisher | International Academy of Ecology and Environmental Sciences |
| record_format | Article |
| series | Network Biology |
| spelling | doaj.art-e9584d2c62d34cb099fba3cfa11dc1e32022-12-22T01:38:22ZengInternational Academy of Ecology and Environmental SciencesNetwork Biology2220-88792022-09-011238196Using the binary representation of arc capacity in a polynomial time algorithm for the constrained maximum flow problem in directed networksMuhammad Tlas0Scientific Services Department, Atomic Energy Commission, P. O. Box 6091, Damascus, SyriaIn 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.http://www.iaees.org/publications/journals/nb/articles/2022-12(3)/constrained-maximum-flow-problem-in-directed-networks.pdfmaximum flow problemscaling algorithmpolynomial time algorithmaugmenting path methodnetwork flow |
| spellingShingle | Muhammad Tlas Using the binary representation of arc capacity in a polynomial time algorithm for the constrained maximum flow problem in directed networks Network Biology maximum flow problem scaling algorithm polynomial time algorithm augmenting path method network flow |
| title | Using the binary representation of arc capacity in a polynomial time algorithm for the constrained maximum flow problem in directed networks |
| title_full | Using the binary representation of arc capacity in a polynomial time algorithm for the constrained maximum flow problem in directed networks |
| title_fullStr | Using the binary representation of arc capacity in a polynomial time algorithm for the constrained maximum flow problem in directed networks |
| title_full_unstemmed | Using the binary representation of arc capacity in a polynomial time algorithm for the constrained maximum flow problem in directed networks |
| title_short | Using the binary representation of arc capacity in a polynomial time algorithm for the constrained maximum flow problem in directed networks |
| title_sort | using the binary representation of arc capacity in a polynomial time algorithm for the constrained maximum flow problem in directed networks |
| topic | maximum flow problem scaling algorithm polynomial time algorithm augmenting path method network flow |
| url | http://www.iaees.org/publications/journals/nb/articles/2022-12(3)/constrained-maximum-flow-problem-in-directed-networks.pdf |
| work_keys_str_mv | AT muhammadtlas usingthebinaryrepresentationofarccapacityinapolynomialtimealgorithmfortheconstrainedmaximumflowproblemindirectednetworks |