Contraction network for solving maximum flow problem

Abstract

In this paper, we present a novel idea to solve maximum flow problem in the directed networks. Given a directed flow network which we call original network here, we propose a method of Contracting Neighbor-node-set Approach (CNA) based on Quotient Space Theory. It selects some nodes from fine-grained original network as equivalence class to form a new node in the new network. The coarse-grained new network is called quotient network. Then we apply classic algorithms on quotient network to solve the maximum flow of original network. The performance in practice of our algorithm is better than that of classic algorithms and the method of simplifying network. Experimental results show that CNA can approximate accurately solve the maximum flow of original network. The correctness of maximum flow is over 95%. At the same time, the node scale reduces to 55.45% of node scale of original network and edge scale reduces to 32.10% of edge scale of original network, averagely.