A Polynomial Time Algorithm for the Minimum Cost Flow Problem

  • M. Tlas

Abstract


An efficient polynomial time algorithm for solving minimum cost flow problems has been proposed in this paper. This algorithm is basically based on
successive divisions of capacities by multiples of two, and it solves the minimum cost flow problem as a sequence of O(n2 ) shortest path problems on residual
networks with n nodes and runs in O(n2m r ) time, where m is the number of arcs and 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 is illustrated using the proposed algorithm.



 

Published
2018-05-11
How to Cite
TLAS, M.. A Polynomial Time Algorithm for the Minimum Cost Flow Problem. GSTF Journal of Mathematics, Statistics and Operations Research (JMSOR), [S.l.], v. 2, n. 1, may 2018. ISSN 2251-3396. Available at: <http://dl6.globalstf.org/index.php/jmsor/article/view/1538>. Date accessed: 16 dec. 2018.