Home

Network Biology, 2025, 15(2): 48-66
[XML] [EndNote] [RefManager] [BibTex] [ Full PDF (173K)] [Comment/Review Article]

Article

A bit-arc capacity scaling algorithm for the maximum flow problem subjected to box constraints on the flow vector in digraph

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

Received 31 October 2024;Accepted 10 December 2024;Published online 23 December 2024;Published 1 June 2025
IAEES

Abstract
A bit-arc capacity scaling algorithm to solve the maximal flow problem subjected to box constraints on the flow vector in directed network has been presented. The algorithm is mainly based on successive divisions of capacities by multiples of two. It solves the maximal flow problem as a sequence of O(n2) Dijkstra's shortest path between two nodes in the defined residual network with n nodes and m arcs. It is proven that, the algorithm's complexity was estimated to be no more than O(n2mr) arithmetic operations in the worst case to reach the maximum vector flow through the directed network. Where r denotes to the smallest integer greater than or equal to log B, and B denotes to the largest arc capacity of the network. A numerical example has been illustrated using the proposed algorithm.

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


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


Translate page to: