Tesis "Construcción de Covering Arrays en el Dominio de Grafos"
Sustentante: José Carlos Pérez Torres
Director: Dr. José Torres Jiménez
Sinodales: Dr. Ricardo Landa Becerra, Dr. Héctor Hugo Avilés Arriaga
Resumen:
Los covering arrays (CAs) son objetos combinatorios que han sido ampliamente usados para realizar de manera eficiente pruebas de software y de hardware.
Uno de los retos importantes en el dominio de CAs es la construcción de ellos con el menor número de renglones (menor número de casos de prueba). La mayor parte de los trabajos reportados en este dominio, utilizan para la construcción de CAs una representación matricial, en este trabajo se presenta un enfoque original que utiliza una representación en el dominio de grafos.
En el dominio de grafos un clique es un subgrafo completo (i.e. para cada pareja de nodos existe un arco). Un clique maximal es un subgrafo completo que no puede hacerse crecer con un nodo más.
Después de resolver el mapeo biyectivo entre matrices y grafos, el problema de construcción de CAs en el dominio de grafos se reduce a construir el menor número de Cliques Maximales (cada clique equivale a un caso de prueba).
En la tesis se desarrollaron cuatro algoritmos principales: un algoritmo exacto, un algoritmo voraz, un algoritmo metaheurístico y un algoritmo de post-procesamiento.
Los resultados mejoran de manera significativa el estado del arte de algoritmos equivalentes. Es relevante que parte de los resultados han sido publicados en una revista indizada en el JCR (Journal Citation Reports).