Differences

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

--- courses:cs211:winter2012:journals:lee:home [2012/04/02 20:14] – [Section 7.5: A First Application: The Bipartite Matching Problem] davisl
+++ courses:cs211:winter2012:journals:lee:home [2012/04/02 21:15] (current) – [Section 7.7: Extensions to the Maximum-Flow Problem] davisl
@@ Line 123: / Line 123: @@
 ==== Section 7.5: A First Application: The Bipartite Matching Problem ====
-The Ford-Fulkerson algorithm not only solves the Maximum-Flow Problem but also the Bipartite Matching Problem. The Bipartite Matching Problem is determining what is the largest subset of edges of some graph such that each node appears at most once in a particular matching. The minimum cut returned from the Ford-Fulkerson Algorithm is the largest matching in a given graph.
+The Ford-Fulkerson algorithm not only solves the Maximum-Flow Problem but also the Bipartite Matching Problem. The Bipartite Matching Problem is determining what is the largest subset of edges of some graph such that each node appears at most once in a particular matching. The minimum cut returned from the Ford-Fulkerson Algorithm is the largest matching in a given graph. The runtime of the algorithm in solving the Bipartite Matching problem is O(mn) and the explanation is on page 370. To determine if a particular matching is perfect, the size of the subset of some nodes |A|, must be less than the size of the rest of the nodes. The proof is on page 372.
+==== 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, 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.