Análisis del espacio de soluciones del problema de relleno mínimo mediante cómputo evolutivo

Ponente(s): Fernando Ignacio Becerra López

En el contexto de programación semidefinida positiva, surgen matrices dispersas que se pueden asociar a grafos. Que el grafo sea cordal permite descomponer la matriz en submatrices simétricas y definidas positivas (mediante sus cliques). Desafortunadamente, esto no es común en aplicaciones prácticas. En particular, encontrar una extensión cordal mínima de un grafo es un problema bien conocido de teoría de grafos y es NP-completo. Este trabajo propone asociar cada extensión cordal con una permutación de números naturales mediante grafos de eliminación y explorar el espacio de soluciones utilizando algoritmos evolutivos. Este método no solo busca encontrar soluciones óptimas, sino también analizar el comportamiento del espacio de permutaciones asociadas y sus implicaciones estructurales.