Problema de L(2,1)-etiquetado bajo un enfoque heurístico

PABLO ROMANO; ISABEL MÉNDEZ-DÍAZ; PAULA ZABALA

Ciudad de Buenos Aires

Simposio; Simposio Argentino de Investigación Operativa, 45 JAIIO: Jornadas Argentinas de Informática; 2016

Sociedad Argentina de Informática e Investigación Operativa

Dados un grafo G(V,E), h y k dos enteros positivos, un L(h,k)-etiquetado es un etiquetado de los vértices que cumple que las etiquetas asignadas a dos vértices adyacentes dieren en por lo menos h y si dos vértices tienen un adyacente en común entonces sus etiquetas dieren en al menos k. El objetivo del problema de L(h,k)-etiquetado es, dado un grafo G y l en N, decidir si existe un L(h,k)- etiquetado de G con máxima etiqueta l. El caso particular de h = 1 y k = 0 es el clásico problema de coloreo de vértices de un grafo.Si bien el problema tiene gran interés en el área de teoría de grafos, también surge como un modelo adecuado en la problemática de redes de comunicacin. Por ejemplo, en las redes de celulares el área de servicio está dividida en un número de celdas, a cada una de las cuales se le asigna una frecuencia para satisfacer la demanda local. Se pueden producir dos tipos de interferencias que se deben evitar. Una de ellas son las colisiones directas, que se dan cuando celdas con zonas de alcance sobrepuestas utilizan frecuencias cercanas. Para evitarlas, celdas vecinas deben tener frecuencias alejadas. Las otras son las colisiones ocultas, una celda no debe recibir señales de una misma frecuencia desde dos celdas.Para evitarlas, las celdas que transmiten a una misma celda deben utilizarfrecuencias distintas.La noción de L(h,k)-etiquetado fue introducida por Griggs y Yeh en el caso especial de h = 2 y k = 1 en el contexto de problemas de asignación de frecuencias en redes de radiodifusión, en este mismo trabajo demuestran que este caso particular es NP-difícil.Dada la condición de problema NP-difícil, en este trabajo proponemos diferentes heurísticas y analizamos su performance en grafos generados al azar.