engleski

Performance of a Parallel Excess Scaling Algorithm

The maximum flow problem is one of the classical network flow problems. In this paper we discuss the excess scaling algorithm for solving the maximum flow problem, and develop its parallel version. Our assumed model of computation is a shared-memory multiprocessor. We describe a concrete implementation of the parallel algorithm based on the PVM package, and present the obtained numerical results.

etwork; maximum flow problem; scaling; parallel algorithm; PVM; experiment

nije evidentirano