METHOD FOR FINDING MAXIMUM VOLUME AND MINIMUM CUT IN A NETWORK OF INTERCONNECTED NODES

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