Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/76610
Type: Artigo de periódico
Title: A PARALLEL IMPLEMENTATION OF THE PUSH-RELABEL ALGORITHM FOR THE MAXIMUM FLOW PROBLEM
Author: ANDERSON, R
SETUBAL, JC
Abstract: We describe an efficient parallel implementation of the push-relabel maximum flow algorithm for a shared-memory multiprocessor. Our main technical innovation is a method that allows the 'global relabeling' heuristic to be executed concurrently with the main algorithm; this heuristic is essential for good performance in practice. We present performance results from a Sequent Symmetry for five input distributions. On these five input distributions we achieve speedups in the range 6.2-8.8 with 16 processors, relative to the parallel program with 1 processor (4.1-7.2 when compared to our best sequential program). We consider these speedups very good and we provide evidence that hardware effects and insufficient parallelism in certain inputs are the main obstacles to achieving better performance. (C) 1995 Academic Press, Inc.
Editor: Academic Press Inc Jnl-comp Subscriptions
Rights: fechado
Identifier DOI: 10.1006/jpdc.1995.1103
Date Issue: 1995
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
WOSA1995RV17300002.pdf1 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.