Differences

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

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision
Previous revision
courses:cs211:winter2014:journals:gabi:home [2014/04/02 01:12] – [Chapter 7.5] tremogcourses:cs211:winter2014:journals:gabi:home [2014/04/02 01:21] (current) – [Chapter 7.7] tremog
Line 1847: Line 1847:
  
 (7.13) In Every flow network the max value of an s-t flow is equal to the minimum capacity of an s-t cut.  (7.13) In Every flow network the max value of an s-t flow is equal to the minimum capacity of an s-t cut. 
 +
 **Algorithms:** **Algorithms:**
  
Line 1858: Line 1859:
  
 Very very little. Very very little.
 +
 +**Key Points:**
 +
 +In a sense, (7.8) looks weaker than (7.6) does since it is only an inequality rather can than equality. However, this becomes extremely useful for us, since the right-hand side is independent of any particular flow f.
  
 Readability (scale: 1-10): Readability (scale: 1-10):
Line 1908: Line 1913:
 ==== Chapter 7.7 ==== ==== Chapter 7.7 ====
  
-//**0.0: **//+//**7.7Extensions to the Max-Flow Problem**//
  
 +**Summary:**
  
 +Many issues that can be solved with the Max-Flow problem have essentially nothing to do with the fact that it models traffic in a network. Who knew? It also helps with problems that have nontrivial combinatorial search components. It is very useful because it can be solved in poly-time with O(Mc) time because of the F-F algorithm.
  
-**Summary:**+One of these problems is the :Circulations with demands: algorithm. For example, what if you had multiple sources and multiple sinks. In this problem, instead of maxing the flow value, we have to consider a problem in which the sources have fixed supply values and the sinks have fixed demands values and our job is to meet these demands. 
  
 +(7:51) The Graph G has a feasible circulation with demands (dv) if and only if for all cuts (A,B)
 +
 +
 +If all of the capacities and demands in G are integers and there is a feasible circulation, then there is a feasible circulation that is integer-valued.  
  
  
 **Algorithms:** **Algorithms:**
  
 + Once again, the F-F algorithm from section one.
  
  
 **Questions:** **Questions:**
  
 +Where is the psudo-code? :(
  
 **What made sense?:** **What made sense?:**
 +
 +The real world application. I don't know why but I can visualize this problem well. Maybe not real world, but this is much less of an abstraction than the ones in 7.5 and 7.2
 +
 +**Key Points:**
 +
 +Many issues that can be solved with the Max-Flow problem have essentially nothing to do with the fact that it models traffic in a network. Who knew?
 +
 +**Readability (1-10):**
 +
 +7. No psudeo-code :(
 +
 +
  
courses/cs211/winter2014/journals/gabi/home.1396401121.txt.gz · Last modified: 2014/04/02 01:12 by tremog
CC Attribution-Noncommercial-Share Alike 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0