Chaitin-Briggs算法解釋

Question

我使用了它，但我還沒有找到關於此主題的一些好的材料。

我在哪裏可以找到關於Chaitin-Briggs圖着色算法的更多信息？或者有人可以解釋它是如何工作的？

Answer 1

Chaitin算法的關鍵洞察力叫做< R規則，如下所示。

給定包含小於R的節點N的圖G，如果圖G'（其中G'是G且節點N被移除）是R可着色的，則G是可着色的。證明在一個方向上是明顯的：如果圖G可以用R顏色着色，則可以在不改變着色的情況下創建圖G'。在另一個方向上，假設我們有G'的R-着色。由於N具有小於R的程度，所以至少有一種顏色不適用於與N相鄰的節點。我們可以用這種顏色對N進行着色。

的算法如下：

While G cannot be R-colored 
    While graph G has a node N with degree less than R 
     Remove N and its associated edges from G and push N on a stack S 
    End While 
    If the entire graph has been removed then the graph is R-colorable 
     While stack S contains a node N 
      Add N to graph G and assign it a color from the R colors 
     End While 
    Else graph G cannot be colored with R colors 
     Simplify the graph G by choosing an object to spill and remove its node N from G 
     (spill nodes are chosen based on object’s number of definitions and references) 
End While 

的所述蔡廷布裏格斯算法的複雜度是因爲溢出的問題的O（N 2）。如果圖G在一些點上只有節點R或更大的節點，那麼圖G只能是R可着色的。當一個圖很容易R可着色時，單次迭代的代價爲O（n），因爲我們在圖中進行兩次訪問，每次刪除或添加一個節點。但是溢出會帶來額外的複雜性，因爲在G變成R可着色之前，我們可能需要溢出任意數量的節點。因爲我們灑每一個節點，我們讓通過這個Register allocation algorithm