A method for finding maximum volume and minimum cut in a network of interconnected nodes

摘要

An improved method for finding a maximum volume minimum cutset in a network of interconnected nodes, applicable to any system that can be reduced to such network including telecommunication network, traffic network, computer networks, layouts, hydraulic networks etc. According to the invention an equivalent network is derived by replacing all nodes other then source and sink by two interconnected nodes, a conventional method applying augmenting path algorithm identifies then a cutset. If the feasible cutset is not achieved than a reduced network is constructed by directly connecting the member nodes of identified cutset to the source node and repeating the above process for the reduce network until a feasible cutset is achieved.