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