A polynomial time algorithm for the maximal constrained network flow problem based on the bit-arc capacity scaling technique
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 o...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
International Academy of Ecology and Environmental Sciences
2023-12-01
|
| Series: | Network Biology |
| Subjects: | |
| Online Access: | http://www.iaees.org/publications/journals/nb/articles/2023-13(4)/maximal-constrained-network-flow-problem.pdf |
| _version_ | 1827766739754024960 |
|---|---|
| author | Muhammad Tlas |
| author_facet | Muhammad Tlas |
| author_sort | Muhammad Tlas |
| collection | DOAJ |
| description | 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.
|
| first_indexed | 2024-03-11T11:45:14Z |
| format | Article |
| id | doaj.art-0ed7ae09a9704990aa6ba28815ce206f |
| institution | Directory Open Access Journal |
| issn | 2220-8879 |
| language | English |
| last_indexed | 2024-03-11T11:45:14Z |
| publishDate | 2023-12-01 |
| publisher | International Academy of Ecology and Environmental Sciences |
| record_format | Article |
| series | Network Biology |
| spelling | doaj.art-0ed7ae09a9704990aa6ba28815ce206f2023-11-09T11:53:15ZengInternational Academy of Ecology and Environmental SciencesNetwork Biology2220-88792023-12-01134122136A polynomial time algorithm for the maximal constrained network flow problem based on the bit-arc capacity scaling techniqueMuhammad Tlas0Scientific Services Department, Atomic Energy Commission, P. O. Box 6091, Damascus, SyriaAn 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. http://www.iaees.org/publications/journals/nb/articles/2023-13(4)/maximal-constrained-network-flow-problem.pdfmaximum flow problembit-capacity scaling algorithmpolynomial time algorithmaugmenting path methodnetwork flow |
| spellingShingle | Muhammad Tlas A polynomial time algorithm for the maximal constrained network flow problem based on the bit-arc capacity scaling technique Network Biology maximum flow problem bit-capacity scaling algorithm polynomial time algorithm augmenting path method network flow |
| title | A polynomial time algorithm for the maximal constrained network flow problem based on the bit-arc capacity scaling technique |
| title_full | A polynomial time algorithm for the maximal constrained network flow problem based on the bit-arc capacity scaling technique |
| title_fullStr | A polynomial time algorithm for the maximal constrained network flow problem based on the bit-arc capacity scaling technique |
| title_full_unstemmed | A polynomial time algorithm for the maximal constrained network flow problem based on the bit-arc capacity scaling technique |
| title_short | A polynomial time algorithm for the maximal constrained network flow problem based on the bit-arc capacity scaling technique |
| title_sort | polynomial time algorithm for the maximal constrained network flow problem based on the bit arc capacity scaling technique |
| topic | maximum flow problem bit-capacity scaling algorithm polynomial time algorithm augmenting path method network flow |
| url | http://www.iaees.org/publications/journals/nb/articles/2023-13(4)/maximal-constrained-network-flow-problem.pdf |
| work_keys_str_mv | AT muhammadtlas apolynomialtimealgorithmforthemaximalconstrainednetworkflowproblembasedonthebitarccapacityscalingtechnique AT muhammadtlas polynomialtimealgorithmforthemaximalconstrainednetworkflowproblembasedonthebitarccapacityscalingtechnique |