An O(n2log n) parallel max-flow algorithm

DOI10.1016/0196-6774(82)90013-XMaRDI QIDQ3942729zbMATH OpenOpenAlexWikidataFDO

Authors 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 complexitydirected flow networkmaximum flowsynchronized parallel algorithm

Mathematics Subject Classification ID

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

Cited in

(28)

• An O(n log n log log n) parallel maximum matching algorithm for bipartite graphs
• 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
• 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
• 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
• Finding maximum matching for bipartite graphs in parallel
• A decentralized flow redistribution algorithm for avoiding cascaded failures in complex networks
• Sequential and parallel algorithms for minimum flows.
• An auction algorithm for the max-flow problem
• Efficient implementation of a synchronous parallel push-relabel algorithm
• TBGMax: leveraging two-boundary graph pattern for lossless maximum-flow acceleration
• A self-stabilizing algorithm for the maximum flow problem
• Inverse shortest path models based on fundamental cycle bases
• Parallel algorithms for the maximum flow problem with minimum lot sizes
• Trade-offs between communication throughput and parallel time
• A lower bound for the shortest path problem
• More efficient parallel flow algorithms
• Scalable high-quality hypergraph partitioning
• 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
• Finding all nearest neighbors for convex polygons in parallel: A new lower bound technique and a matching algorithm

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

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