4

無向グラフに複数のソースと宛先のペアがあるとします。複数のペアに対して互いに素なパスを生成したい。そのような問題の複雑さは何でしょうか? これらのペアのエッジ分離パスを見つけるための多項式ヒューリスティックはありますか? (つまり、s1 と d1 の間のパスには、s2 と d2 の間のパスと共通のエッジがあってはなりません)

4

2 に答える 2

2

これは、マルチ商品フローの問題の変種のように見えます: http://en.wikipedia.org/wiki/Multi-commodity_flow_problem

各ソース/シンク ペアを新しい商品として扱い、エッジにユニット ウェイトを与えて、互いに素なパスを適用します。ここで、単位容量を持つこのクラスの MCFP の近似値を文献で検索します。

于 2013-10-16T18:39:15.557 に答える
1

2 つのソースと 2 つのシンクの場合でも、問題は NP 困難です。どのソースがどのシンクと一致するかを気にするのをやめると、多項式で解けるようになります。

于 2013-10-16T18:43:43.887 に答える