Topic
IC4NOTICE: developerWorks Community will be offline May 29-30, 2015 while we upgrade to the latest version of IBM Connections. For more information, read our upgrade FAQ.
1 reply Latest Post - ‏2013-02-13T10:21:44Z by SystemAdmin
SystemAdmin
SystemAdmin
754 Posts
ACCEPTED ANSWER

Pinned topic how to find overall min-cut separating some node pairs, not all node pairs

‏2012-12-19T01:19:13Z |
As we know, now there is efficient algorithms to find the overall min-cut in a directed graph, e.g. Hao and Orlin (1994).

Now my problem is to find an overall min-cut just separating some given node pairs, not all the node pairs. For example, I have an 8-node digraph with capacities on each arc and want to find the overall min-cut 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
Updated on 2013-02-13T10:21:44Z at 2013-02-13T10:21:44Z by SystemAdmin
  • SystemAdmin
    SystemAdmin
    754 Posts
    ACCEPTED ANSWER

    Re: how to find overall min-cut separating some node pairs, not all node pairs

    ‏2013-02-13T10:21:44Z  in response to SystemAdmin
    What you are looking for is a minimum s-t cut. For example, you can apply the Edmonds-Karp algorithm (or any other min cut / max flow algorithm) for this.

    Tobias