# Item

ITEM ACTIONSEXPORT

Released

Report

#### A lower bound for the nondeterministic space complexity of contextfree recognition

##### Fulltext (public)

MPI-I-91-115.pdf

(Any fulltext), 3MB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Cheriyan, J., Hagerup, T., & Mehlhorn, K.(1991). *A lower
bound for the nondeterministic space complexity of contextfree recognition* (MPI-I-91-115). Saarbrücken: Max-Planck-Institut
für Informatik.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-7B1A-7

##### Abstract

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