サイクルの最大重み独立集合問題(パスグラフの変更)

Nov 23 2020

問題:頂点に負でない重みを持つグラフG =(V、E)。必要な出力: n個の頂点v1を持つサイクルCの最大総重量の独立した頂点のセット(隣接していない)。。。vn(i <nごとに、viはvi + 1に接続され、vnはv1に接続され、これらはCの唯一のエッジです)。

この問題は、この問題の修正です。パスグラフの最大重み独立集合問題

サイクルを含まないパスグラフの元の問題の解決策は次のとおりです。

a[i] = max(a[i - 1], a[i - 2] + w[i])

これは、ISがvnを含むものと含まないもののいずれかであり、各サブ問題がnの一部のみを取り、分割統治法であるため、実行時間がO(n)の最悪の場合であるためです。

サイクル変更の場合、これが私のアプローチです。

  1. ISにはv1が含まれていますが、vnは含まれていません。
  2. ISにはvnが含まれていますが、v1は含まれていません
  3. ISにはv1もvnも含まれていません。

方程式がサイクル変更のパスグラフ(上に表示)と同じになるかどうか、およびその記述方法がわかりません。また、実行時間が同じになるかどうかもわかりません。上手。助けてください。

回答

1 DavidEisenstat Nov 23 2020 at 22:23

ケースが重ならないようにする必要はありません。v1を除外するソリューションの最大値とvnを除外するソリューションの最大値が見つかった場合、v1とvnの両方を含むソリューションはないため、全体の最大値はこれら2つの候補ソリューションのいずれかと一致する必要があります。これらのサブ問題の場合、パスDPはうまく機能します。