%0 Journal Article
%T Modeling the Parallelization of the Edmonds-Karp Algorithm and Application | Chaibou | Computer and Information Science | CCSE
%A Amadou Chaibou
%A Oumarou Si¨¦
%A Ousmane Tessa
%J Home | Computer and Information Science | CCSE
%D 2019
%R 10.5539/cis.v12n3p81
%X 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
%U http://www.ccsenet.org/journal/index.php/cis/article/view/0/40192