𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A Parallel Implementation of the Push-Relabel Algorithm for the Maximum Flow Problem

✍ Scribed by R. Anderson; J.C. Setubal

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
1002 KB
Volume
29
Category
Article
ISSN
0743-7315

No coin nor oath required. For personal study only.

✦ Synopsis

We describe an efficient parallel implementation of the pushrelabel 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. 1995 Academic Press. Inc.

πŸ“œ SIMILAR VOLUMES

A capacity scaling algorithm for the con
A capacity scaling algorithm for the constrained maximum flow problem
✍ Ravindra K. Ahuja; James B. Orlin πŸ“‚ Article πŸ“… 1995 πŸ› John Wiley and Sons 🌐 English βš– 970 KB

## Abstract The constrained maximum flow problem is to send the maximum possible flow from a source node s to a sink node t in a directed network subject to a budget constraint that the cost of flow is no more than __D__. In this paper, we consider two versions of this problem: (i) when the cost of

A parallel QR algorithm for the nonsymme
A parallel QR algorithm for the nonsymmetric eigenvalue problem
✍ Daniel Boley; Robert Maier; Joung Kim πŸ“‚ Article πŸ“… 1989 πŸ› Elsevier Science 🌐 English βš– 973 KB

This paper describes a prototype parallel algorithm for approximating eigenvalues of a dense nonsymmetric matrix on a linear, synchronous processor array. The algorithm is a parallel implementation of the explicitly-shifted QR, employing n distributed-memory processors to deliver all eigenvalues in