16 Sep
2009
16 Sep
'09
8:40 p.m.
Hi David, David Doria wrote:
2) I guess my phrasing wasn't very clear. Basically what it would be nice to do is specify a list of nodes that are definitely on one side of the cut, and a second list of nodes which are definitely on the other side of the cut. The cut would then be constrained so that these two sets indeed lie on different sides of the cuts. VERY simple examples (a graph with < 10 nodes) should be provided to demonstrate (1) and (2).
Oh. I am not sure this is actually still an easy problem, complexity-wise. In any case it seems to be not easily reformulated into a standard s-t min-cut problem. Regards, Sebastian