标题: how to find overall min-cut separating some node pairs, not all node pairs [打印本页] 作者: xyw2013 时间: 2012-12-20 10:59 标题: how to find overall min-cut separating some node pairs, not all node pairs As we know, now there is efficient algorithms to find the overall min-cut in a directed graph, e.g. Hao and Orlin (1994).& n. I) l% V' R% y+ E3 q6 ^
7 w1 T0 Y A/ F: a2 s! RNow 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. ; M9 Z. ~( I9 A5 g. p& p: F
0 y" Y. Z7 \% O8 J9 f( I8 q0 x