COMP 360 Lecture Notes - Lecture 9: If And Only If, Maximum Flow Problem

• School: McGill University
• Department: Computer Science (Sci)
• Course: COMP 360
• Professor: Adrian R Vetta

Document Summary

If it is positive - this is the amount i want to consume at this node. (demand > supply) If it is negative - this is the amount i want to produce at this node (supply > demand> Circulation is a function (like flow): - for each e in e: 0 <= f(e) <= c. f(e) where c = capacity. There is a way to encode the circulation problem from the max flow problem. I add edges from the source to all the "supply" nodes with edge capacities = I add edges from the "demand" nodes to the sink nodes with edge capacities = With this graph i have a circulation iff the max flow = sum of edges leaving the source. In the new graph g" all the edges leaving "s" and all edges entering "t" are satiated with the flow which is equal to the capacity of the edge.