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.