Spiegazione dell'algoritmo di Chaitin-Briggs

Question

L'ho cercato su google ma non ho trovato alcun materiale valido su questo argomento.

Dove è possibile trovare ulteriori informazioni sull'algoritmo di colorazione grafica Chaitin-Briggs? O qualcuno può spiegare come funziona?

Answer 1

L'intuizione chiave dell'algoritmo di Chaitin è chiamata la regola di grado < R che è la seguente.

Dato un grafico G che contiene un nodo N con grado inferiore a R, G è R-colorabile se il grafico G ', dove G' è G con nodo N rimosso, è R-colorabile. La dimostrazione è ovvia in una direzione: se un grafico G può essere colorato con colori R, allora il grafico G 'può essere creato senza modificare la colorazione. Nell'altra direzione supponiamo di avere una R-colorazione di G '. Poiché N ha un grado inferiore a R deve esserci almeno un colore che non è in uso per un nodo adiacente a N. Possiamo colorare N con questo colore.

L'algoritmo è il seguente:

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 

La complessità dell'algoritmo Chaitin-Briggs è O (n2) a causa del problema della fuoriuscita. Un grafico G non può essere solo R-colorable se ad un certo punto il grafico ridotto G 'ha solo nodi di grado R o maggiori. Quando un grafico è facilmente R-colorabile, il costo di una singola iterazione è O (n) perché facciamo due viaggi attraverso il grafico e rimuoviamo o aggiungiamo un nodo ogni volta. Ma lo sversamento comporta un'ulteriore complessità perché potremmo aver bisogno di versare un numero arbitrario di nodi prima che G diventi R-colorabile. Per ogni nodo versiamo noi facciamo un altro viaggio attraverso l'algoritmo lineare

Si può anche passare attraverso questo Register allocation algorithm