Differences

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

--- courses:cs211:winter2012:journals:garrett:entries:week_10 [2012/04/04 05:49] – 7.5 garrettheath4
+++ courses:cs211:winter2012:journals:garrett:entries:week_10 [2012/04/04 05:55] (current) – 7.7 garrettheath4
@@ Line 24: / Line 24: @@
 === 7.7: Extensions to the Maximum-Flow Problem ===
-There are a lot of interesting problems that are based on the maximum-flow problem.  One such problem is a network flow
+There are a lot of interesting problems that are based on the maximum-flow problem.  One such problem is a network flow in which each node also has its own supply and demand.  A node with a supply is a node that brings a certain amount flow traffic into the graph.  A node with a demand is a node that acts as a destination node for a certain amount of flow traffic out of the graph.
+Another problem is a network flow in which each edge has a lower bound in addition to its usual upper bound (capacity).  In this kind of problem, simply add the lower bound of an edge to the demand of both of its endpoint nodes.