Processor-efficient implementation of a maximum flow algorithm

DOI10.1016/0020-0190(91)90097-2MaRDI QIDQ1178222zbMATH OpenOpenAlexFDO

Authors Andrew V. Goldberg

Publication date 26 June 1992

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(91)90097-2

zbMATH Keywords

Maximum Distance Dischargeparallel implementationspush-relable method

Mathematics Subject Classification ID

Parallel numerical computation (65Y05) Analysis of algorithms and problem complexity (68Q25) Distributed algorithms (68W15) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Review text

The push-relabel method was developed by the author and \textit{R. E. Tarjan} [J. Assoc. Comput. Mach. 35, No. 4, 921-940 (1988; Zbl 0661.90031)]. The Maximum Distance Discharge (MDD) algorithm is another variation of the generic push-relabel method. In this paper the author describes two parallel implementations of the MDD algorithm. Both implementations use \(p=O(\sqrt m)\) processors. The first implementation runs in \(O(n^ 2\log(2m/n+p)(\sqrt m/p))\) time using \(O(m+n \log n)\) memory. The second one uses \(O(m+n)\) amount of memory and runs in \(O(n^ 2\log n(\sqrt m/p))\) time (\(n\) and \(m\) denote the number of vertices and the number of arcs in the input network). Both implementations achieve near-optimal speedup for up to a linear number of processors.

Recommendations

• scientific article; zbMATH DE number 515925
• On implementing push-relabel method for the maximum flow problem
• A new approach to the maximum-flow problem
• Efficient implementation of a synchronous parallel push-relabel algorithm

Cites work

• A Fast and Simple Algorithm for the Maximum Flow Problem
• An O(n2log n) parallel max-flow algorithm
• Analysis of Preflow Push Algorithms for Maximum Network Flow
• Deterministic coin tossing with applications to optimal parallel list ranking
• scientific article; zbMATH DE number 4204092 (Why is no real title available?)
• scientific article; zbMATH DE number 3825195 (Why is no real title available?)
• scientific article; zbMATH DE number 3475221 (Why is no real title available?)
• scientific article; zbMATH DE number 3225808 (Why is no real title available?)
• Parallel Prefix Computation
• Parallelism in random access machines
• The maximum flow problem is log space complete for P
• The Parallel Evaluation of General Arithmetic Expressions
• Ultracomputers

Cited in

(11)

• Parallel cardinality stacks and an application
• Processor optimization for flow graphs
• Characterizing multiterminal flow networks and computing flows in networks of small treewidth
• Sequential and parallel algorithms for minimum flows.
• A distributed mincut/maxflow algorithm combining path augmentation and push-relabel
• Efficient preflow push algorithms
• Efficient implementation of a synchronous parallel push-relabel algorithm
• scientific article; zbMATH DE number 515925 (Why is no real title available?)
• Efficient algorithms for the maximum concurrent flow problem
• More efficient parallel flow algorithms
• Quick max-flow algorithm

This page was built for publication: Processor-efficient implementation of a maximum flow algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1178222)