Jump to content

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

shaon
in Applied Mathematics

Featured Replies

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 only 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

Archived

This topic is now archived and is closed to further replies.

Go to topic listing

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.

Configure browser push notifications
Chrome (Android)
  1. Tap the lock icon next to the address bar.
  2. Tap Permissions → Notifications.
  3. Adjust your preference.
Chrome (Desktop)
  1. Click the padlock icon in the address bar.
  2. Select Site settings.
  3. Find Notifications and adjust your preference.