Department of Applied Mathematics & Physics, Kyoto Univiversity
Technical Report #97002 (January, 1997)
A fast algorithm for finding a maximum free multiflow in an inner Eulerian network and some generalizations
by Toshihide Ibaraki, Alexander V. Karzanov and Hiroshi Nagamochi
Let N=(G,T,c) be a network, where G is an
undirected graph with n nodes and m edges, T is a set of p
specified nodes of G, called terminals , and each edge e of G
has a nonnegative integer capacity c(e). If the total capacity of edges
with one end at v is even for every non-terminal node v, then N is
called inner Eulerian. A free multiflow is a collection of flows
between arbitrary pairs of terminals such that the total flow through
each edge does not exceed its capacity.
In this paper we first generalize a method in Karzanov [1979a] to find
a maximum integer free multiflow in an inner Eulerian network,
in $O(\vphi(n,m) \log p)$ time, where $\vphi$ is the complexity of finding a maximum flow
between two terminals. Next we
extend our algorithm to solve the so-called laminar locking problem
on multiflows, also in $O(\vphi(n,m) \log p)$ time.
We then consider analogs of the above problems in inner balanced
directed networks, which means that for each non-terminal node v,
the sums of
capacities of arcs entering v and leaving v are the same. We show that
for such a network a maximum integer free multiflow can be constructed in
$O(\vphi(n,m) \log p+n2m)$ time, and then extend this result to the
corresponding locking problem.