Estudio experimental del problema 2 + p-COL aleatorio
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...
- Autores:
-
Cruz Rodes, Roberto
Galvis Santamaría, Andrés David
- Tipo de recurso:
- Article of investigation
- Fecha de publicación:
- 2011
- Institución:
- Universidad de Antioquia
- Repositorio:
- Repositorio UdeA
- Idioma:
- spa
- OAI Identifier:
- oai:bibliotecadigital.udea.edu.co:10495/46361
- Acceso en línea:
- https://hdl.handle.net/10495/46361
- Palabra clave:
- Matemáticas
Mathematics
Álgebra
Algebra
- Rights
- openAccess
- License
- http://creativecommons.org/licenses/by-nc-nd/4.0/
| Summary: | 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. |
|---|