如何找到分離一些節點對的整體最小切割

如我們所知，現在有高效的算法來找到有向圖中的總體最小切割，例如，郝和奧林（1994）。如何找到分離一些節點對的整體最小切割

現在我的問題是找到一個整體最小切割只是分離一些給定的節點對，而不是所有的節點對。例如，我在每個弧上有一個8節點的有向圖，並且想要找到最小切割分離8和1,6和3,7和1.

非常感謝。

來源

2012-12-19 shaon

你想解決最小多重分割問題，這是NP-Hard，但也在文獻中進行了廣泛的研究。例如http://scholar.google.be/scholar?q=minimum+multicut+directed+graph&btnG=&lr=

來源

2012-12-20 15:03:31 Dave

我想你不明白我的問題。正如我所提到的那樣，現在有高效的算法來查找分離所有節點對的整體最小切割。在這裏，我想要一個很好的算法來找到僅僅分離一些節點對的總體最小切割。 – shaon

我想我確實理解你的答案:)。你想*找到總體最小切割只是分離一些節點對。*這就是所謂的*多*剪切。這個問題是一個開放的研究問題，據我所知，沒有「好」的算法，因爲這個問題太難了。大多數算法都是隨機的，或者只處理圖表的某個子類，例如http://arxiv.org/abs/1206.3999 所以你應該看看哪種算法最適合你的需求。 – Dave

非常感謝。我想我沒有清楚地解釋我的問題。我的問題不同於最小多重分割問題，即找到一組最小權重邊，這些邊的去除將每對給定源和彙集分隔開。但我的問題是要確定每個節點對的所有切割的最小值。例如，我有一個4節點的有向圖和節點對{1,4}，{2,4}和{1,3}。然後，我想要找到最小的一個，其中最小的一個是分割1和4，最小的是分割2和4，最小的是分割1和3. – shaon

如何找到分離一些節點對的整體最小切割

回答

相關問題