An O(n2log n) parallel max-flow algorithm

DOI10.1016/0196-6774(82)90013-XzbMath0483.90044OpenAlexW2007470648WikidataQ56813860 ScholiaQ56813860MaRDI QIDQ3942729

Uzi Vishkin, Yossi Shiloach

Publication date: 1982

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(82)90013-x

zbMATH Keywords

computational complexitymaximum flowsynchronized parallel algorithmdirected flow network

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Deterministic network models in operations research (90B10)

Related Items (26)

Sequential and parallel algorithms for minimum flows. ⋮ Finding maximum matching for bipartite graphs in parallel ⋮ An O(n log n log log n) parallel maximum matching algorithm for bipartite graphs ⋮ Efficient Implementation of a Synchronous Parallel Push-Relabel Algorithm ⋮ An auction algorithm for the max-flow problem ⋮ The parallel complexity of finding a blocking flow in a 3-layer network ⋮ An improvement of Goldberg, Plotkin and Vaidya's maximal node-disjoint paths algorithm ⋮ A decentralized flow redistribution algorithm for avoiding cascaded failures in complex networks ⋮ TBGMax: leveraging two-boundary graph pattern for lossless maximum-flow acceleration ⋮ Finding all nearest neighbors for convex polygons in parallel: A new lower bound technique and a matching algorithm ⋮ A self-stabilizing algorithm for the maximum flow problem ⋮ Processor-efficient implementation of a maximum flow algorithm ⋮ Worst case behavior of the Dinic algorithm ⋮ Expected parallel time and sequential space complexity of graph and digraph problems ⋮ A new Karzanov-type \(O(n^ 3)\) max-flow algorithm ⋮ Trade-offs between communication throughput and parallel time ⋮ Inverse Shortest Path Models Based on Fundamental Cycle Bases ⋮ Parallel algorithms for the maximum flow problem with minimum lot sizes ⋮ A lower bound for the shortest path problem ⋮ A parallel algorithm for finding a blocking flow in an acyclic network ⋮ A heuristic for blocking flow algorithms ⋮ Characterizing multiterminal flow networks and computing flows in networks of small treewidth ⋮ A simple version of Karzanov's blocking flow algorithm ⋮ A parallel-design distributed-implementation (PDDI) general-purpose computer ⋮ An optimal parallel connectivity algorithm ⋮ The maximum flow problem: A max-preflow approach

This page was built for publication: An O(n2log n) parallel max-flow algorithm