Estudio experimental del problema 2 + p−COL aleatorio

Abstract

El problema 2 + p−COL aleatorio interpola suavemente desde el problema polinomial 2−COL aleatorio al problema NP-Completo 3−COL aleatorio. En este artículo se presenta un extenso estudio experimental del comportamiento de la transición de fase y el costo computacional de este problema. Se introdujo un nuevo parámetro para el estudio experimental de la transición de fase. Los resultados para el n de la transición de fase se ajustan a los valores obtenidos teóricamente por otros autores. El estudio del costo computacional, realizado en la frontera de la fase, mostró un escalamiento polinomial para p 0,7 y exponencial para p 0,8.