Communication Network Theory
On Flows in Simple Bidirected and Skew-Symmetric Networks
M. A. Babenko M. V. Lomonosov Moscow State University, Faculty of Mechanics and Mathematics
Abstract:
We consider a simple directed network. Results of Karzanov, Even, and Tarjan
show that the blocking flow method constructs a maximum integer flow in this network in
$O(m\min(m^{1/2},n^{2/3}))$ time (hereinafter,
$n$ denotes the number of nodes, and
$m$ the number of
arcs or edges). For the bidirected case, Gabow proposed a reduction to solve the maximum
integer flow problem in
$O(m^{3/2})$ time. We show that, with a variant of the blocking flow method,
this problem can also be solved in
$O(mn^{2/3})$ time. Hence, the gap between the complexities
of directed and bidirected cases is eliminated. Our results are described in the equivalent
terms of skew-symmetric networks. To obtain the time bound of
$O(mn^{2/3})$, we prove that
the value of an integer
$s$–
$s'$ flow in a skew-symmetric network without parallel arcs does not
exceed
$O(Un^2/d^2)$, where
$d$ is the length of the shortest regular
$s$–
$s'$ path in the split network
and
$U$ is the maximum arc capacity. We also show that any acyclic integer flow of value
$v$ in a
skew-symmetric network without parallel arcs can be positive on at most
$O(n\sqrt v)$ arcs.
UDC:
621.394.74:519.2
Received: 01.06.2006
Revised: 08.08.2006
Fulltext:
PDF file (2179 kB)
