Patent ID: 7188328

Claim:
A method for finding a maximum volume and minimum cutset in a network of interconnected nodes having a source node and at least one sink node, the method comprising: a. constructing a derived network for a given sink node by replacing all nodes other than the source and sink nodes by a set of first and second interconnected nodes connected by a single bridging edge such that a bridging edge connects an output of a first node to an input of a second node, the first node receiving inputs from previous nodes of the network, and the second node providing outputs to next nodes of the network; b. assigning to each bridging edge a capacity of unity and to each non-bridging edge a capacity of infinity; c. applying an augmenting path algorithm to identify all distinct paths from the source node to a sink node; d. identifying a member of a maximum volume and minimum cutset as a first saturated node encountered while traversing from the source node to the sink node; e. discarding those member nodes that have all the output nodes as members of the set; f. checking if a feasible cutset is not achieved, then i. constructing a reduced network by connecting the member of the cutset to the source node directly; ii. repeating the steps c–e for the reduced network; and g. repeating steps a–f for each sink node of the network.