7

私はそれをグーグルで検索しましたが、このトピックに関する良い資料が見つかりませんでした.

Chaitin-Briggs グラフの色付けアルゴリズムに関する詳細情報はどこで入手できますか? または、誰かがそれがどのように機能するかを説明できますか?

4

1 に答える 1

12

Chaitinのアルゴリズムに対する重要な洞察は、次のように次数<Rルールと呼ばれます。

次数がＲ未満のノードＮを含むグラフＧが与えられると、グラフＧ'（Ｇ'はノードＮが除去されたＧである）がＲ着色可能である場合、ＧはＲ着色可能である。証明は一方向で明らかです。グラフGをR色で着色できる場合、色を変更せずにグラフG'を作成できます。他の方向では、G'のR-coloringがあると仮定します。Nの次数はR未満であるため、Nに隣接するノードに使用されていない色が少なくとも1つ存在する必要があります。この色で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カラー化できる場合、グラフを2回トリップし、毎回1つのノードを削除または追加するため、1回の反復のコストはO（n）です。ただし、GがRカラー可能になる前に任意の数のノードをスピルする必要がある場合があるため、スピルするとさらに複雑になります。こぼれたノードごとに、線形アルゴリズムを介して別のトリップを行います

このレジスタ割り当てアルゴリズムを実行することもできます

于 2013-01-18T13:35:31.080 に答える