MPI-I-91-120
An $O(n^3)$-time maximum-flow algorithm
Cheriyan, Joseph and Hagerup, Torben and Mehlhorn, Kurt
November 1991, 30 pages.
.
Status: available - back from printing
We show that a maximum flow in a network with $n$ vertices
can be computed deterministically in $O({{n^3}/{\log n}})$
time on a uniform-cost RAM.
For dense graphs, this improves the
previous best bound of $O(n^3)$.
The bottleneck in our algorithm is a combinatorial
problem on (unweighted) graphs.
The number of operations executed on flow variables is
$O(n^{8/3}(\log n)^{4/3})$,
in contrast with
$\Omega(nm)$ flow operations for all previous algorithms,
where $m$ denotes the number of edges in the network.
A randomized version of our algorithm executes
$O(n^{3/2}m^{1/2}\log n+n^2(\log n)^2/
\log(2+n(\log n)^2/m))$
flow operations with high probability.
For the special case in which
all capacities are integers bounded by $U$,
we show that a maximum flow can be computed
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1991-120
BibTeX
@TECHREPORT{CheriyanHagerupMehlhorn91,
AUTHOR = {Cheriyan, Joseph and Hagerup, Torben and Mehlhorn, Kurt},
TITLE = {An $O(n^3)$-time maximum-flow algorithm},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPI-I-91-120},
MONTH = {November},
YEAR = {1991},
ISSN = {0946-011X},
}