Differences

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

Link to this comparison view

Both sides previous revisionPrevious revision
courses:cs211:winter2014:journals:gabi:home [2014/04/02 01:12] – [Chapter 7.2] tremogcourses:cs211:winter2014:journals:gabi:home [2014/04/02 01:21] (current) – [Chapter 7.7] tremog
Line 1913: 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.1396401154.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