El algoritmo de Chaitin es un algoritmo de asignación de registros de coloración de gráficos de abajo hacia arriba que utiliza el costo/grado como su métrica de derrame . Recibe su nombre en honor a 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. Era una extensión de un artículo anterior de 1981 sobre el uso de coloración de grafos 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.