Chaitin-Briggs Algorithm explanation

Question

I googled it but I haven't found some good material about this topic.

Where can I find more information about Chaitin-Briggs graph-coloring algorithm? Or can somebody explain how it works?

Answer 1

The key insight to Chaitin’s algorithm is called the degree < R rule which is as follows.

Given a graph G which contains a node N with degree less than R, G is R-colorable iff the graph G’, where G’ is G with node N removed, is R-colorable. The proof is obvious in one direction: if a graph G can be colored with R colors then the graph G’ can be created without changing the coloring. In the other direction supposed we have an R-coloring of G’. Since N has a degree of less than R there must be at least one color that is not in use for a node adjacent to N. We can color N with this color.

The algorithm is as follows:

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

The complexity of the Chaitin-Briggs algorithm is O(n2) because of the problem of spilling. A graph G will only fail to be R-colorable if at some point the reduced graph G’ only has nodes of degree R or greater. When a graph is easily R-colorable the cost of a single iteration is O(n) because we make two trips through the graph and either remove or add one node each time. But spilling brings in additional complexity because we may need to spill an arbitrary number of nodes before G becomes R-colorable. For every node we spill we make another trip through the linear algorithm

You can also go through this Register allocation algorithm