[[courses:cs211:winter2012:journals:virginia:chapter7]]
Trace: • chapterthreesectionv • chapterthreesectionii • chapterthreesectionvi • summer_2008_research_assistants
Show page
Recent ChangesSitemap

Differences

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

Link to this comparison view

Both sides previous revisionPrevious revision
courses:cs211:winter2012:journals:virginia:chapter7 [2012/04/04 02:58] – [Section 7: Extensions to the Maximum Flow Problem] lovellvcourses:cs211:winter2012:journals:virginia:chapter7 [2012/04/04 02:59] (current) – lovellv
Line 12: Line 12:
  
 We can implement this algorithm in O(mC) time, where m is the number of edges and C is the maximum flow we could send out of the source node s.  We can implement this algorithm in O(mC) time, where m is the number of edges and C is the maximum flow we could send out of the source node s. 
 +
 +Readability: 8
  
 ===== Section 2: Maximum Flow and Minimum Cuts in a Network ===== ===== Section 2: Maximum Flow and Minimum Cuts in a Network =====
Line 18: Line 20:
  
 Note that if we did not have integer capacities the FF algorithm would not necessarily terminate, but the max flow - min cut theorem still holds.  Note that if we did not have integer capacities the FF algorithm would not necessarily terminate, but the max flow - min cut theorem still holds. 
 +
 +Readability: 8
  
 ===== Section 5: The Bipartite Matching Problem ===== ===== Section 5: The Bipartite Matching Problem =====
  
 In this section, we see how to solve the bipartite matching problem using our new algorithm.  First we need to create a flow network from our original graph.  This network will have directed edges from nodes in X to nodes in Y, in place of any undirected edge between a node in X and a node in Y.  Then we add a source node with an edge from it to each node in X, and a sink node with an edge to it from each node in Y.  Each edge has capacity 1.  Finally we run the FF algorithm.  This gives us the size of the maximum matching (since the capacities are 1, each node can appear at most once).  We can then use the flow to find the matching.  We can find this matching in O(mn) time.   In this section, we see how to solve the bipartite matching problem using our new algorithm.  First we need to create a flow network from our original graph.  This network will have directed edges from nodes in X to nodes in Y, in place of any undirected edge between a node in X and a node in Y.  Then we add a source node with an edge from it to each node in X, and a sink node with an edge to it from each node in Y.  Each edge has capacity 1.  Finally we run the FF algorithm.  This gives us the size of the maximum matching (since the capacities are 1, each node can appear at most once).  We can then use the flow to find the matching.  We can find this matching in O(mn) time.  
 +
 +Readability: 8
  
 ===== Section 7: Extensions to the Maximum Flow Problem ===== ===== Section 7: Extensions to the Maximum Flow Problem =====
Line 29: Line 35:
 Networks can also have lower bounds for edges that require a certain flow.  Suppose we have a circulation problem with lower bounds.  Then we can just reduce the maximum capacity of each edge by the lower bound and reduce the demand of each node by L = lower bound of edge in - lower bound of edge out.  Now we have a network without lower bounds and the idea above can be applied.          Networks can also have lower bounds for edges that require a certain flow.  Suppose we have a circulation problem with lower bounds.  Then we can just reduce the maximum capacity of each edge by the lower bound and reduce the demand of each node by L = lower bound of edge in - lower bound of edge out.  Now we have a network without lower bounds and the idea above can be applied.         
          
-   +Readability: 8   
                              
courses/cs211/winter2012/journals/virginia/chapter7.1333508315.txt.gz · Last modified: by lovellv
Show pageOld revisions
Media ManagerBack to top
CC Attribution-Noncommercial-Share Alike 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0