0

Let G = (V, E) be a directed graph, with source s belonging to V, sink t belonging to V, and nonnegative edge capacities. Give a exist a polynomial time algorithm to decide whether G has a unique minimum cut (basically an s-t capacity strictly less than that of all other s-t cuts)?

I am a bit stuck, so finding minimum cut use Folkerson-Ford and then check any other s-t path? Am i missing something here?

2
Contributors
2
Replies
3
Views
5 Years
Discussion Span
Last Post by katisss
This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.