Please use this identifier to cite or link to this item:
|Type:||Artigo de periódico|
|Title:||A PARALLEL IMPLEMENTATION OF THE PUSH-RELABEL ALGORITHM FOR THE MAXIMUM FLOW PROBLEM|
|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|
|Appears in Collections:||Unicamp - Artigos e Outros Documentos|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.