Chaitin-Briggs Algorithmus Erklärung

Question

Ich googelte es, aber ich habe kein gutes Material zu diesem Thema gefunden.

Wo finde ich weitere Informationen über Chaitin-Briggs Graph-Coloring-Algorithmus? Oder kann jemand erklären, wie es funktioniert?

Answer 1

Der Schlüssel Einblick in Chaitin-Algorithmus heißt der Grad < R-Regel, die wie folgt ist.

Gegeben ist ein Graph G, der einen Knoten N mit einem Grad kleiner als R enthält, G ist R-färbbar, wenn der Graph G ', wo G' G mit entferntem Knoten N ist, R-färbbar ist. Der Beweis ist in einer Richtung offensichtlich: Wenn ein Graph G mit R Farben gefärbt werden kann, dann kann der Graph G 'erzeugt werden, ohne die Färbung zu ändern. In der anderen Richtung haben wir eine R-Färbung von G '. Da N einen Grad von weniger als R hat, muss es mindestens eine Farbe geben, die für einen Knoten neben N nicht verwendet wird. Wir können N mit dieser Farbe färben.

Der Algorithmus ist wie folgt:

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 

Die Komplexität des Chaitin-Briggs-Algorithmus ist O (n 2), weil das Problem der zu verschütten. Ein Graph G wird nur dann R-färbbar sein, wenn der reduzierte Graph G 'zu irgendeinem Zeitpunkt nur Knoten mit dem Grad R oder größer aufweist. Wenn ein Graph einfach R-färbbar ist, sind die Kosten für eine einzelne Iteration O (n), weil wir zweimal durch den Graphen gehen und entweder jeweils einen Knoten entfernen oder hinzufügen. Das Verschütten bringt jedoch zusätzliche Komplexität mit sich, da wir möglicherweise eine beliebige Anzahl von Knoten verschütten müssen, bevor G R-färbbar wird. Für jeden Knoten machen wir verschütten wir eine weitere Reise durch den linearen Algorithmus

Sie auch durch diese Register allocation algorithm