7

我用谷歌搜索了它，但我没有找到关于这个主题的一些好材料。

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

4

1 回答 1

12

Chaitin 算法的关键见解称为度数 < R 规则，如下所示。

给定一个图 G，其中包含一个度数小于 R 的节点 N，如果图 G'（其中 G' 是移除了节点 N 的 G）是 R 可着色的，则 G 是 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 之前溢出任意数量的节点。对于我们溢出的每个节点，我们都会通过线性算法进行另一次旅行

你也可以通过这个寄存器分配算法

于 2013-01-18T13:35:31.080 回答