(An) arc-squeezing approach to cut-tree construction for undirected networks

Abstract

An undirected network with n nodes has at most n(n-1)/2 maximum flow values, each being represented in one of n-1 distinct flow values. Defining a free are as an arc in a cycle which is not included in other cycles, it is shown that such a free arc can be squeezed into the rest of the arcs in the cycle with the node-to-node flow still reserved in the network. Then, an arc-squeezing procedure is exploited to break all the cycles contained in the network by its implementing sequentially on each of them and finally to construct a cut-tree, directly transformed from the network. By the arc-squeezing algorithm, multi-terminal network flow problems can be solved in the computational complexity of O(n3), which is much more efficient than any other maximum flow algorithms.