Análisis estadístico del orden computacional de una representación evolutiva aplicada al problema del relleno mínimo.

Ponente(s): Ricardo Pérez Ramírez

El problema del relleno mínimo es un problema clásico y NP-completo que consiste en agregar la menor cantidad de aristas a un grafo G=(V,E) para convertirlo en un grafo cordal. Una forma de abordarlo es mediante la búsqueda de un orden de eliminación de vértices que minimice el número de aristas agregadas. Existen estrategias heurísticas, como el método del grado mínimo o los algoritmos voraces (greedy), que ofrecen buenos resultados en la práctica, aunque sin garantizar una solución óptima. En este trabajo se presenta un análisis estadístico del costo computacional asociado a una estrategia de generación de representaciones iniciales basada en la estructura del grafo. Dicha estrategia esta concebida para ser aplicada en enfoques evolutivos, sin embargo, aquí se examina desde una perspectiva computacional, evaluando cómo varía su complejidad en función del número de vértices y la densidad del grafo. Este enfoque permite construir representaciones iniciales eficientes que aprovechen la información topológica del grafo y que, al mismo tiempo, acoten el espacio de búsqueda, contribuyendo así a mejorar el desempeño de la estrategia evolutiva en este tipo de problemas.