# MPI-I-91-120

## An $O(n^3)$-time maximum-flow algorithm

### Cheriyan, Joseph and Hagerup, Torben and Mehlhorn, Kurt

**MPI-I-91-120**. November** **1991, 30 pages. | Status:** **available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

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

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

91-120.pdf | 23992 KBytes |

Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView |

**URL to this document: **http://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},`

`}`