サブグラフ同型問題をサブセット和問題としてキャストして、サブセット和問題を解くために利用可能な動的計画法を使用して SGI 問題を解くことは可能ですか?
2 に答える
1
はい、できますが、知られているすべての削減は、指数関数的に大きな数の部分和問題を生成します。
(また、宿題検出器が壊れています。)
于 2011-05-02T18:38:19.077 に答える
0
これがどのように行われるのかわかりません。部分和問題の重みとグラフの構造との間にすぐに明確なマッピングはありません。2 つの問題の間の唯一の関係は、部分和問題におけるグラフの部分集合と集合の部分集合です。サブセット合計の疑似ポリタイム (動的プログラミング) アルゴリズムは、一連の数字と制限された合計に対して動作します。この形式でグラフの構造をエンコードする方法があるとは思えません。しかし、これが宿題の問題であることを考えると、私は間違っているかもしれません:)
于 2011-05-02T17:22:07.520 に答える