El algoritmo de Chaitin es un algoritmo de asignación de registros de coloración de gráficos ascendente que utiliza costo/grado como métrica de derrame . Lleva el nombre de su diseñador, Gregory Chaitin . El algoritmo de Chaitin fue el primer algoritmo de asignación de registros que utilizó la coloración del gráfico de interferencia tanto para las asignaciones de registros como para el derrame.
El algoritmo de Chaitin se presentó en el Simposio SIGPLAN sobre construcción de compiladores de 1982 y se publicó en las actas del simposio. Fue una extensión de un artículo anterior de 1981 sobre el uso de coloración de gráficos para la asignación de registros. El algoritmo de Chaitin formó la base de una gran parte de la investigación sobre asignadores de registros.