A lock-free multi-threaded algorithm for the maximum flow problem
Bo Le Hong · Proceedings - IEEE International Parallel and Distributed Processing Symposium · 2008
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\2\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.