engleski

Experimental evaluation of a parallel max-flow algorithm

The maximum flow problem has been studied for over forty years. One of the methods for solving this problem is the generic push-relabel algorithm. In this paper we develop a parallel version of this sequential algorithm. Our assumed model of computation is a shared-memory multiprocessor. We describe a concrete implementation of the algorithm based on the PVM package, and present the obtained numerical results.

network; maximum flow problem; parallel algorithm; PVM; experiment

nije evidentirano