The Research archive provides access to all Research articles published in past issues of Communications of the ACM.
December 2023
From Communications of the ACM
Technical Perspective: Maximum Flow through a Network: A Storied Problem and a Groundbreaking Solution
"Almost-Linear-Time Algorithms for Maximum Flow and Minimum-Cost Flow," by Li Chen et al., comes within striking distance of answering the question: "Does maximum flow have a scalable algorithm?"
From Communications of the ACM
Almost-Linear-Time Algorithms for Maximum Flow and Minimum-Cost Flow
We present an algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with m edges and polynomially bounded integral demands, costs, and capacities in m1+o(1) time.