A fast algorithm for finding a maximum free multiflow in an inner Eulerian network and some generalizatons (Q1280281)

The paper concerns the problem of finding the maximum flow between two terminals in a network \(N = (G,T,c)\) consisting of an undirected graph \(G=(V_{G'}E_{G'})\), a subset \(T\) of nodes of \(G\), called terminals, and a nonnegative integer - valued function \(c: E_G\to Z_+\) of capacities of edges of \(G\). A free multiflow is a collection of flows between arbitrary pairs of terminals such that total flow through each edge does not exceed its capacity. Special networks \(N\) as inner Eulerian network, laminar locking problem, and inner balanced directed network are defined. The paper presents three algorithms: an algorithm for finding an integer maximum free multiflow in an inner Eulerian network, an algorithm for the laminar locking problem and an algorithm for balanced networks. For each of the proposed algorithms the complexity analysis is given.