Seminario del IESTA

El miércoles 27 de octubre de 14 a 15:30 horas tendrá lugar en modalidad semipresencial, en el Salón Multifuncional y por Zoom, un nuevo Seminario del IESTA (SIESTA) titulado Detección de un k-subgrafo denso en un grafo aleatorio a cargo de Manuel Hernández Banadik, del Departamento de Métodos Cuantitativos.

Resumen

El problema de encontrar un subgrafo denso, de tamaño dado k, en un grafo aleatorio se puede ver como una generalización de encontrar un k-clique, es decir, un subgrafo completo de tamaño k.

Tenemos un modelo de la siguiente forma: sea G = (V, E) un grafo aleatorio sorteado bajo un modelo Erdös-Renyi con parámetro p = 1/2. Sobre un conjunto de nodos de tamaño k, se implanta un subgrafo Erdös-Renyi de parámetro 1- delta, para delta pequeño. El caso delta = 0 es el caso del clique implantado.

Los algoritmos, basados en la descomposición espectral de la matriz de adyacencia, que resolvían bien el problema original, fallan ante esta generalización. En esta charla voy a presentar una propuesta de algoritmo para obtener una solución exacta a este problema.

Mail de contacto: Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.