Processor-efficient implementation of a maximum flow algorithm

DOI10.1016/0020-0190(91)90097-2zbMath0754.90024OpenAlexW2025830455MaRDI QIDQ1178222

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

parallel implementationsMaximum Distance Dischargepush-relable method

Mathematics Subject Classification ID

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

Related Items

Sequential and parallel algorithms for minimum flows. ⋮ Parallel cardinality stacks and an application ⋮ A distributed mincut/maxflow algorithm combining path augmentation and push-relabel ⋮ Characterizing multiterminal flow networks and computing flows in networks of small treewidth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The maximum flow problem is log space complete for P
• A Fast and Simple Algorithm for the Maximum Flow Problem
• Analysis of Preflow Push Algorithms for Maximum Network Flow
• Deterministic coin tossing with applications to optimal parallel list ranking
• Parallel Prefix Computation
• Ultracomputers
• An O(n2log n) parallel max-flow algorithm
• The Parallel Evaluation of General Arithmetic Expressions
• Parallelism in random access machines