Patent ID: 7143380
Filing Date: 2006-11-28
Classification: G06F

Abstract:
1. A method for computing flow in a network that comprises at least one source, at least one sink, and a plurality of nodes, comprising: representing the plurality of nodes as a first subset and a second subset, the first subset including a plurality of object nodes and the second subset including a plurality of slot nodes; establishing the at least one source as a virtual source node and the at least one sink as a virtual sink node in the network; establishing an edge from the virtual source node to each object node and an edge from each slot node to the virtual sink node; establishing an initial set of edges from the object nodes to the slot nodes; establishing a respective cost value and a respective capacity value for each edge; computing a minimum cost, maximum capacity solution of a matching of object nodes to slot nodes without considering a constraint, wherein the constraint defines a condition of a valid matching of at least one object node to at least one slot node; and in response to the solution being infeasible as violating the constraint, determining at least one edge, at least one object node, and at least one slot node that violate the constraint, and modifying said network at one or more of the at least one edge, at least one object node, and at least one slot node to discourage said infeasible solution in a next iteration of computation.