Reputation: 557
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