LTM
LTM

Reputation: 557

Finding if a minimum cut in a flow network where we force certain nodes to be in certain sides of the cut

We are given a flow network and two nodes u and v. We want to create an algorithm that tells us whether or not there is a minimum s-t cut so that u belongs to the same side of the cut as the source node s and v belongs to the same side of the cut as the sink node t.

I know how to find a min cut after running Ford-Fulkerson, but since min cuts are not necessarily unique, I'm not sure how to test if there is a min cut with u and s on one side and t and v on another.

Upvotes: 1

Views: 339

Answers (0)

Related Questions