数学建模社区-数学中国

标题: 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).
3 R/ l6 ~& v) Q0 ~( Q' V
, }$ V* u6 f0 h3 S! w3 wNow 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. & o- A9 O8 l" b! l+ s) w

* o7 C% O: H4 Q) y* ^' c' \' M4 {3 i* H* G" O6 z% ^
不好意思,我用英文至少为了把问题说的更清楚一点




欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5