Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2012:journals:lee:home [2012/04/02 20:58] – davisl
+++ courses:cs211:winter2012:journals:lee:home [2012/04/02 21:15] (current) – [Section 7.7: Extensions to the Maximum-Flow Problem] davisl
@@ Line 126: / Line 126: @@
 ==== Section 7.7: Extensions to the Maximum-Flow Problem ===
-In section 7.7, the authors discuss extensions to the Maximum-Flow problem. In the one of these extensions, graph is actually a bipartite graph with a source node connecting a set of nodes labelled as suppliers which are connected to consumers. The set of consumers are in turn connected to a sink node. Each edge has a flow and capacity  and if the difference between the flow and capacity is positive for a given node, then that node is a consumer, otherwise that node would be a supplier.
+In section 7.7, the authors discuss extensions to the Maximum-Flow problem. In the one of these extensions, the graph is similar to the one constructed in the Bipartite Matching Problem with a source node connecting a set of nodes labelled as suppliers which are connected to consumers. The set of consumers are in turn connected to a sink node. Each edge has a flow and capacity  and if the difference between the flow and capacity is positive for a given node, then that node is a consumer, otherwise that node would be a supplier. The goal is to find the best "circulation" that satisfies the demand for a given graph. The above problem description is known as the Circulation Problem. A circulation must satisfy the following conditions: (i) Every flow must be positive and less than or equal to its edge's capacity, (ii) the demand for a particular node will be the difference between the edges that enter and exit the node. The proof is on page 381. The problem can be extended to handle lower bounds on the amount of flow on edges. The proof is on pages 383-384.