是否有一種圖形着色算法，其中可以限制每種顏色的頂點數

我知道圖着色是一個NP完全問題。我想知道如果在可以給定顏色的頂點數量上添加限制會使問題變得更簡單嗎？我似乎無法找到任何這樣做的算法。例如，如果我有一個圖，我想說「這個圖的最小着色是什麼，每種顏色最多有3個頂點」，或者如果它簡化了這個問題「有沒有一種方法可以用4種顏色，每種顏色最多有3個頂點「？是否有一種圖形着色算法，其中可以限制每種顏色的頂點數

謝謝！

來源

2013-04-12 cs54321

由於有人反對r600g bank_swizzle調度，這隻會產生這樣的約束，我不會說它簡化了一些事情，而是我要解決的另一個問題。 Thx雖然問這個問題。 –

這個問題仍然是NP完全的從原始圖着色問題簡單的減少：有n個節點的圖是k可着色的當且僅當圖可以用k種顏色着色並且沒有顏色被分配給更多比n個節點。換句話說，你所說的問題的一般版本將圖着色作爲一種特殊情況，所以它仍然是NP難題。

希望這會有所幫助！

來源

2013-04-12 17:44:15 templatetypedef

謝謝！我很感激！ – cs54321

當你說問題仍然是np-hard時，你是指np-complete？ – Calpis

@Calpis NP-hard應該是正確的，因爲減少意味着這至少與標準圖着色問題一樣困難。 –

我要說的是尋找給定的限制色數的曲線圖的一個K-着色存在可以容易地添加到基於一個確切DSATUR算法[Randall-Brown 72][San Segundo 11]剪枝的搜索空間時一個頂點必須是配色k。無論如何，問題依然存在於NP中。

來源

2014-07-24 11:06:50 chesslover

是否有一種圖形着色算法，其中可以限制每種顏色的頂點數

回答

相關問題