Resumen

Sean G y \bar{G} dos grafos complementarios. Dada una función de penalización en las aristas de G, la rigidez de una k-coloración de(Error rendering LaTeX formula)(Error rendering LaTeX formula)k$-coloración de rigidez mínima. Este trabajo realiza un estudio comparativo de varias técnicas heurísticas: Recocido Simulado, GRASP, y Búsqueda Dispersa. Los resultados aquí presentados son los mejores obtenidos para el PCR.