私たちが知っているように、有向グラフで全体的な最小カットを見つけるための効率的なアルゴリズムがあります。たとえば、Hao と Orlin (1994) です。
今私の問題は、すべてのノードペアではなく、いくつかの特定のノードペアを分離するだけの全体的な最小カットを見つけることです。たとえば、各アークに容量を持つ 8 ノードのダイグラフがあり、8 と 1、6 と 3、7 と 1 を分離する最小カットを見つけたいと考えています。
どうもありがとう。
質問する
423 次
1 に答える
0
NP 困難であるが、文献で広く研究されている最小マルチカット問題を解きたいとします。例http://scholar.google.be/scholar?q=minimum+multicut+directed+graph&btnG=&lr=
于 2012-12-20T15:03:31.510 に答える