
Home

Network Biology, 2023, 13(4): 122-136
[XML] [EndNote] [RefManager] [BibTex] [

Full PDF (849K)] [Comment/Review Article]

Article

A polynomial time algorithm for the maximal constrained network flow problem based on the bit-arc capacity scaling technique

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

Received 3 April 2023;Accepted 10 May 2023;Published online 19 May 2023;Published 1 December 2023
IAEES

Abstract
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(m² 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.

Keywords maximum flow problem;bit-capacity 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/5/11

Translate page to: