A lock-free multi-threaded algorithm for the maximum flow problem

The maximum flow problem is an important graph problem with a wide range of applications. In this paper, we present a lock-free multi-threaded algorithm for this problem. The algorithm is based on the push-relabel algorithm proposed by Goldberg. By using re-designed push and relabel operations, we derive our algorithm that finds the maxi- mumflow with 0{V² E) operations. We demonstrate that as long as a multi-processor architecture supports atomic ´read-update-write´ operations, it will be able to execute the multi-threaded algorithm free of any lock usages. The proposed algorithm is expected to significantly improve the efficiency of solving maximum flow problem on parallel/multi-core architectures.