Home

Network Biology, 2021, 11(2): 82-96
[XML] [EndNote] [RefManager] [BibTex] [ Full PDF (152K)] [Comment/Review Article]

Article

A bit-capacity scaling algorithm for the constrained minimal cost network flow problem

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

Received 11 January 2021;Accepted 20 February 2021;Published 1 June 2021
IAEES

Abstract
A polynomial time algorithm for solving the minimum-cost network flow problem has been proposed in this paper. This algorithm is mainly based on the binary representation of capacities; it solves the minimum-cost flow problem in directed graph of n nodes and m directed arcs as a sequence of O(n2) shortest path problems on residual networks. The algorithm runs in O(n2mr) time, where r is the smallest integer greater than or equal to Log2B, and B is the largest arc capacity of the network. A generalization of this proposed algorithm has been also performed in order to solve the minimum-cost flow problem in a directed network subject to non-negative lower bound on the flow vector. A formulation of both the transportation and the assignment problems, as a minimal cost network flow problem has been also performed. A numerical example has been inserted to illustrate the use of the proposed method.

Keywords minimal cost flow problem;bit-scaling algorithm;polynomial time algorithm;augmenting path method;transportation problem;assignment problem.


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/4/19


Translate page to: