Empaquetamiento de gráficas con algoritmos genéticos

Ponente(s): Maria Fernanda Soria Garcia, José Manuel Gómez Soto

Una malla de n x n es un gráfica simple que consiste de n filas y n columnas de vértices. Denotamos el vértice en la i-ésima fila y la j-ésima columna como (i,j). Todos los vértices en la malla tienen exactamente 4 vecinos, excepto los que están en la frontera (i=1, i=n, j=1 o j=n). Un subconjunto P de V es un conjunto de empaquetamiento de G (o 2-packing) si para cada u y v que pertenecen a V se tiene que N[u] es vacía. El número de empaquetamiento de G es el tamaño máximo de algún conjunto de empaquetamiento de G. En esta ponencia presentaremos como empaquetar gráficas de mallas cuadradas utilizando algoritmos genéticos.