As we know, now there is efficient algorithms to find the overall mincut in a directed graph, e.g. Hao and Orlin (1994).
Now my problem is to find an overall mincut just separating some given node pairs, not all the node pairs. For example, I have an 8node digraph with capacities on each arc and want to find the overall mincut separating some node pairs such as 8 and 1, 6 and 3, 7 and 1.
The algorithm of Hao and Orlin (1994) cannot solve my problem.
Thanks a lot.
Shaon
Topic
This topic has been locked.
1 reply
Latest Post
 20130213T10:21:44Z by SystemAdmin
ACCEPTED ANSWER
Pinned topic how to find overall mincut separating some node pairs, not all node pairs
20121219T01:19:13Z

Answered question
This question has been answered.
Unanswered question
This question has not been answered yet.
Updated on 20130213T10:21:44Z at 20130213T10:21:44Z by SystemAdmin

ACCEPTED ANSWER
Re: how to find overall mincut separating some node pairs, not all node pairs
20130213T10:21:44Z in response to SystemAdminWhat you are looking for is a minimum st cut. For example, you can apply the EdmondsKarp algorithm (or any other min cut / max flow algorithm) for this.
Tobias