An Efficient Algorithm to Solve the Maximal Flow Problems  
Author Shin-Guang Chen

 

Co-Author(s)

 

Abstract The maximal ow problem is a classical optimization problem since 1954. Many researchers have contributed methods to concur such problems including the famous Ford-Fulkerson method, etc. However, the complexity of Ford-Fulkerson method is O(Eβλ) where E is the number of edges, β is the number of paths and λ is the maximal value of flow. Also, their method cannot converge when the flow is not integer. This paper proposes an ecient algorithm to solve the maximal flow problems with integer or real flow in them. The complexity of the proposed algorithm is shown as O(β log(β)), and indicates that the proposed algorithm is more efficient than the famous ones. Several examples are explored to show the application of the proposed algorithm.

 

Keywords sort, Euclidean vector space, network reliability, lower boundary vectors, upper boundary vectors
   
    Article #:  23-157
 
Proceedings of the 23rd ISSAT International Conference on Reliability and Quality in Design
August 3-5, 2017 - Chicago, Illinois, U.S.A.