Revista de Matemática: Teoría y Aplicaciones ISSN Impreso: 1409-2433 ISSN electrónico: 2215-3373

OAI: https://revistas.ucr.ac.cr/index.php/matematica/oai
Coloración de gráficas suaves
PDF

Palabras clave

coloración de graficas suaves
teoría de graficas
coloración sobre vértices
soft graph coloring
graph theory
coloring on vertexes

Cómo citar

Lara-Velázquez, P., Gutiérrez-Andrade, M. Ángel, De-Los-Cobos-Silva, S. G., & Rincón-García, E. A. (2015). Coloración de gráficas suaves. Revista De Matemática: Teoría Y Aplicaciones, 22(2), 311–323. https://doi.org/10.15517/rmta.v22i2.20838

Resumen

En este trabajo se propone un modelo de Coloración en Gráficas Suaves donde se colorea con base en ponderaciones sobre las aristas de la gráfica. Se muestra que este modelo es muy flexible e incluye otros problemas similares, tales como los problemas de Coloración Mínima, Coloración Equitativa, Coloración de Gráficas Débiles y Coloración Robusta. Se proponen también un modelo binario lineal de solución y algunas instancias de prueba.
https://doi.org/10.15517/rmta.v22i2.20838
PDF

Citas

Burke, E.K.; Jackson, K.; Kingston, J.; Weare, R. (1997) “Automated university timetabling: the state of the art”, Comput. J. 40: 565–571.

Burke, E.K.; Petrovic, S. (2002) “Recent research directions in automated timetabling”, Eur. J. Opl. Res. 140: 266–280.

Cangalovic, M.; Schreuder, J.A.M. (1991) “Exact colouring algorithm for weighted graphs applied to timetabling problems with lectures of different lengths”, Eur. J. Opl. Res. 51: 248–258.

Carter, M.W.; Laporte, G. (1998) “Recent developments in practical course timetabling”, in: E.R. Burke & M. Carter (Eds) Practice and Theory of Automated Timetabling II, Second International Conference, PATAT’97, Toronto, Canada: 3–19.

Cowen, L.; Goddard, W.; Jesurum C.E. (1997) “Defective Coloring Revisited”, J. Graph. Theory 24(3): 205–219.

Diestel, R. (2000) Graph Theory. Springer-Verlag, New York.

Kuhn, F. (2009) “Weak graph colorings: distributed algorithms and applications”, SPAA’09, Calgary, Alberta, Canada: 138–144.

McCollum, B.; Schaerf, A.; Paechter, B.; McMullan, P.; Lewis, R.; Parkes, A.; Di Gaspero, L.; Qu, R.; Burke E. (2009) “Setting the research agenda in automated timetabling: the Second International Timetabling Competition”, INFORMS Journal on Computing, doi: 10.1287/ijoc.1090.0320.

Meyer, W. (1973) “Equitable coloring”, American Mathematical Monthly (Mathematical Association of America) 80: 920–922, doi: 10.2307/2319405

Nandhini, M.; Kanmani, S. (2009) “A survey of simulated annealing methodology for university course timetabling”, International Journal of Recent Trends in Engineering 1: 255–257.

Ramírez, J. (2001) Extensiones del problema de coloración de gráfos. Tesis Doctoral, Universidad Complutense de Madrid, Madrid, España.

Roberts, F.S. (1991) “T-colorings of graphs: recent results and open problems´´, Discrete Math. 93: 229–245.

Wang, F.; Xu, Z. (2013) “Heuristics for robust graph coloring”, J. Heuristics 19: 529–548. doi: 10.1007/s10732-011-9180-4

Yañez, J.; Ramírez, J. (2003) “The robust coloring problem”, European Journal of Operational Research, 148(3): 546–558.

Comentarios

Creative Commons License

Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-CompartirIgual 4.0.

Derechos de autor 2015 Pedro Lara-Velázquez, Miguel Ángel Gutiérrez-Andrade, Sergio G. De-Los-Cobos-Silva, Eric Alfredo Rincón-García

Descargas

Los datos de descargas todavía no están disponibles.