众所周知，现在有有效的算法可以在有向图中找到整体最小割，例如 Hao 和 Orlin (1994)。
现在我的问题是找到一个整体最小切割，只分离一些给定的节点对，而不是所有的节点对。例如，我有一个 8 节点有向图，每个弧上都有容量，并且想要找到分隔 8 和 1、6 和 3、7 和 1 的最小割。
非常感谢。
问问题
423 次
1 回答
0
您想解决最小多割问题，这是 NP-Hard，但在文献中也进行了广泛研究。例如http://scholar.google.be/scholar?q=minimum+multicut+directed+graph&btnG=&lr=
于 2012-12-20T15:03:31.510 回答