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

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

We then consider analogs of the above problems in