Original scientific paper
Experimental Evaluation of a Parallel Max-Flow Algorithm
Goranka Nogo
; Department of Mathematics, University of Zagreb, Bijenicka 30, 10000 Zagreb, Croatia
Robert Manger
orcid.org/0000-0003-0953-6517
; Department of Mathematics, University of Zagreb, Bijenicka 30, 10000 Zagreb, Croatia
Abstract
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.
Keywords
network; maximum flow problem; parallel algorithm; PVM; experiment
Hrčak ID:
150182
URI
Publication date:
30.9.1999.
Visits: 577 *