CSE 550 Combinatorial algorithms and intractability, Fall 2009, Arizona State University.
Saturday, September 5, 2009
Homework 2
hi, Just to clarify some doubts. In Q1 part a, we assume the min cut= max flow and just improve an existing max flow algorithm for the answer?. Also do we need to find the cut set, in addition to the value?
If you are only interested in the value of the min-cut then this question becomes trivial. So, you should also output the cut itself (it's enough to output one of the two sides of the cut).
Also, have you posted the lecture notes for network flow? I couldn't find them on Blackboard or the course home page...
ReplyDeleteAssume you know all we've covered in class.
ReplyDeleteIf you are only interested in the value of the min-cut then this question becomes trivial. So, you should also output the cut itself (it's enough to output one of the two sides of the cut).