Modeling the Parallelization of the Edmonds-Karp Algorithm and Application


  •  Amadou Chaibou    
  •  Ousmane Moussa Tessa    
  •  Oumarou Sié    

Abstract

Many optimization problems can be reduced to the maximum flow problem in a network. However, the maximum flow problem is equivalent to the problem of the minimum cut, as shown by Fulkerson and Ford (Fulkerson & Ford, 1956). There are several algorithms of the graph’s cut, such as the Ford-Fulkerson algorithm (Ford & Fulkerson, 1962), the Edmonds-Karp algorithm (Edmonds & Karp, 1972) or the Goldberg-Tarjan algorithm (Goldberg & Tarjan, 1988). In this paper, we study the parallel computation of the Edmonds-Karp algorithm which is an optimized version of the Ford-Fulkerson algorithm. Indeed, this algorithm, when executed on large graphs, can be extremely slow, with a complexity of the order of O|V|.|E|2 (where |V| designates the number of vertices and |E| designates the number of the edges of the graph). So why we are studying its implementation on inexpensive parallel platforms such as OpenMp and GP-GPU. Our work also highlights the limits for parallel computing on this algorithm.



This work is licensed under a Creative Commons Attribution 4.0 License.
  • Issn(Print): 1913-8989
  • Issn(Onlne): 1913-8997
  • Started: 2008
  • Frequency: quarterly

Journal Metrics

(The data was calculated based on Google Scholar Citations)

Google-based Impact Factor (2018): 18.20

h-index (January 2018): 23

i10-index (January 2018): 90

h5-index (January 2018): 11

h5-median(January 2018):17

Contact