Chaitin-Briggs算法解释

Question

我搜索了它,但我没有找到关于这个主题的一些好材料.

在哪里可以找到有关Chaitin-Briggs图形着色算法的更多信息？或者有人可以解释它是如何工作的？

Answer 1

对Chaitin算法的关键见解称为度<R规则,如下所示.

给定包含程度小于R的节点N的图G,如果图G'(其中G'是G且去除了节点N)的G是R可着色的,则R是可着色的.证明在一个方向上是显而易见的:如果图形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

由于溢出问题,Chaitin-Briggs算法的复杂性为O(n2).如果在某一点,简化图G'仅具有度R或更大的节点,则图G将不能是R可着色的.当图形容易R可着色时,单次迭代的成本是O(n),因为我们通过图形进行两次跳转并且每次移除或添加一个节点.但溢出会带来额外的复杂性,因为在G变为R-colorable之前,我们可能需要溢出任意数量的节点.对于我们溢出的每个节点,我们通过线性算法进行另一次旅行

您也可以通过此寄存器分配算法