A Hybrid Parallel Implementation for the Maximum Flow Problem
Marco A. Stefanes, Luiz Fernando Alvino · 2018
The maximum flow problem is a classical combinatorial problem with many applications. In this work a hybrid parallel algorithm using both multi-core and many-core technologies for computing the maximum flow in a network is presented. The proposed implementation is applicable in OpenMP/CUDA-enabled computing environment. To improve the performance two strategies were implemented: an adaptive approach where the algorithm alternate GPU/CPU processing according to the number of active nodes and implementations of the global relabeling and gap relabeling heuristics on multi-core approach. When compared against the best sequential implementation, the speedups range from 2.36 to 5.38 in several kinds of graph. Results show that the proposed algorithm is faster than previous parallel implementations on CPU/GPUs for all kinds of tested graphs.