An Asynchronous Multithreaded Algorithm for the Maximum Network Flow Problem with Nonblocking Global Relabeling Heuristic

In this paper, we present a novel asynchronous multithreaded algorithm for the maximum network flow problem. The algorithm is based on the classical push-relabel algorithm, which is essentially sequential and requires intensive and costly lock usages to parallelize it. The novelty of the algorithm i... View More