A fast maximum flow algorithm

DOI10.1002/NET.22001MaRDI QIDQ6065305zbMATH OpenOpenAlexFDO

Authors James B. Orlin

Publication date 11 December 2023

Published in Networks (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1910.04848, https://hdl.handle.net/1721.1/134021

zbMATH Keywords

contractionnetwork flowsmaximum flowsstrongly polynomialscaling algorithmsflow-return forest

Mathematics Subject Classification ID

Flows in graphs (05C21)

Abstract: In 2013, Orlin proved that the max flow problem could be solved in $O(nm)$ time. His algorithm ran in $O(nm+m^{1.94})$ time, which was the fastest for graphs with fewer than $n^{1.06}$ arcs. If the graph was not sufficiently sparse, the fastest running time was an algorithm due to King, Rao, and Tarjan. We describe a new variant of the excess scaling algorithm for the max flow problem whose running time strictly dominates the running time of the algorithm by King et al. Moreover, for graphs in which $m=O(nlogn)$, the running time of our algorithm dominates that of King et al. by a factor of $O(loglogn)$.

Recommendations

• Improved Time Bounds for the Maximum Flow Problem
• Max flows in \(O(nm)\) time, or better
• AO(nm log(U/n)) time maximum flow algorithm
• An $o(n^3 )$-Time Maximum-Flow Algorithm
• Publication:4038695

Cites work

• scientific article; zbMATH DE number 3475221 (Why is no real title available?)
• A Fast and Simple Algorithm for the Maximum Flow Problem
• A Faster Deterministic Maximum Flow Algorithm
• A Faster Strongly Polynomial Minimum Cost Flow Algorithm
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• A data structure for dynamic trees
• A new approach to the maximum-flow problem
• Beyond the flow decomposition barrier
• Improved Time Bounds for the Maximum Flow Problem
• Max flows in \(O(nm)\) time, or better
• Maximal Flow Through a Network
• Network flows. Theory, algorithms, and applications.

Cited in

(5)

• An incremental algorithm for the maximum flow problem
• Quick max-flow algorithm
• A new approach to computing maximum flows using electrical flows
• Geometric matching and bottleneck problems
• Maximum flow and minimum-cost flow in almost-linear time

This page was built for publication: A fast maximum flow algorithm

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