1

数日前、リソース割り当ての既知の問題を解決するために間隔グラフに取り組んでいました。多項式時間でこの問題 (彩色数) を解決し、間隔グラフの各頂点の色を提供する貪欲なアプローチがあることがわかっているためです (一般的なグラフで彩色数を見つける問題は NP-Complete (Karp による 3-充足可能性削減) です。

私は疑問に思っていました: 区間グラフではないグラフがあった場合、それは長さ > 3 の弦のないサイクルが 1 つだけあるためです (それを削除するとグラフが区間グラフになるというエッジがあります)、この種のグラフで彩色数を見つける問題を NP-Complete にしますか?

4

1 に答える 1

0

間隔グラフの色付けアルゴリズムが機能しないエッジが 1 つだけある場合は、それを削除します。区間グラフ アルゴリズムを実行します。削除されたエッジの 2 つの端点の色が異なる場合は、完了です。それ以外の場合、アルゴリズムが使用した色の数を C とします。2 つの端点に対してすべて (C は 2 つを選択) の固定色を試し、間隔グラフ アルゴリズムを再試行します。Cカラーで成功すれば完了です。それ以外の場合は、C+1 の色が必要になるため、エンドポイントの 1 つを選択して、一意の色を指定します。

ポリ時間で取り外し可能なエッジを見つけることができると思います。

于 2011-01-23T00:05:09.290 に答える