Čejtinov algoritam
Čejtinov algoritam je odozdo-nagore algoritam za bojenje grafova koji koristi alokaciju registara, a kao meru za pražnjenje registara koristi jedinicu cena/stepen. Ovaj algoritam osmislio je Gregori Čejtin, po kome nosi ime. Čejtinov algoritam je bio prvi algoritam, koji koristi alokaciju registara, koji je iskoristio bojenje grafova kako za alokaciju registara tako i za njihovo pražnjenje.

Čejtinov algoritam je predstavljen i objavljen 1982. na SIGPLAN Simpozijumu o konstrukciji kompilatora. To je bio nastavak ranijeg rada iz 1981. godine koji se bavio bojenjem grafova za alokaciju registara. Čejtinov algoritam predstavlja osnovu velikog dela istraživanja koja se bave alokacijom registara.

Pseudokod 
Neka je dat graf -{G}-, koji sadrži čvorove -{N}- stepena manjeg od -{R}-. Graf -{G}- je -{R}--bojiv ukoliko graf -{G}-' (gde je -{G}-' graf -{G}- sa uklonjenim čvorom -{N}-) -{R}--bojiv.

Dokaz je očigledan.
 Pretpostavimo da je graf -{G R}--bojiv. Onda nam je i graf -{G}-' sigurno R-bojiv.
 Pretpostavimo da nam je graf -{G' R}--bojiv. Pošto nam je čvor -{N}- stepena manjeg od -{R}- mora postojati bar jedna boja kojom nije obojen nijedan susedni čvor čvora -{N}-. Tom bojom možemo obojiti -{N}-. Dakle -{G}- je -{R}--bojiv.

Pseudokod algoritma glasi:
  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
Složenost Čejtinovog algoritma je:

Reference

Literatura 
 -{Gregory Chaitin Register allocation and spilling via graph coloring}-
 -{Gregory Chaitin Register allocation and spilling via graph coloring}-

Графовски алгоритми
Čejtinov algoritam je odozdo-nagore algoritam za bojenje grafova koji koristi alokaciju registara , a kao meru za pražnjenje registara koristi jedinicu cena / stepen . Ovaj algoritam osmislio je Gregori Čejtin , po kome nosi ime . Čejtinov algoritam je bio prvi algoritam , koji koristi alokaciju registara , koji je iskoristio bojenje grafova kako za alokaciju registara tako i za njihovo pražnjenje . Čejtinov algoritam je predstavljen i objavljen na SIGPLAN Simpozijumu o konstrukciji kompilatora . To je bio nastavak ranijeg rada iz godine koji se bavio bojenjem grafova za alokaciju registara . Čejtinov algoritam predstavlja osnovu velikog dela istraživanja koja se bave alokacijom registara . Pseudokod Neka je dat graf -{ G }- , koji sadrži čvorove -{ N }- stepena manjeg od -{ R } - . Graf -{ G }- je -{ R } --bojiv ukoliko graf -{ G }- ' ( gde je -{ G }- ' graf -{ G }- sa uklonjenim čvorom -{ N }- ) -{ R } --bojiv . Dokaz je očigledan . Pretpostavimo da je graf -{ G R } --bojiv . Onda nam je i graf -{ G }- ' sigurno R-bojiv . Pretpostavimo da nam je graf -{ G ' R } --bojiv . Pošto nam je čvor -{ N }- stepena manjeg od -{ R }- mora postojati bar jedna boja kojom nije obojen nijedan susedni čvor čvora -{ N }- . Tom bojom možemo obojiti -{ N }- . Dakle -{ G }- je -{ R } --bojiv . Pseudokod algoritma glasi : 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 Složenost Čejtinovog algoritma je : Reference Literatura -{ Gregory Chaitin Register allocation and spilling via graph coloring }- -{ Gregory Chaitin Register allocation and spilling via graph coloring }- Графовски алгоритми