Día y lugar: Lunes 04/05 a las 14 hs. en la sala de reuniones 2119 del Pabellón 0+infinito.
Expositor: Camilo Vera
Título: Problema DIM, problema PED, y más problemas.
Resumen:
En esta charla, hablaremos de dominación eficiente y perfecta de aristas en grafos. Un dominating induced matching (DIM) es un conjunto M de aristas tal que toda arista de E(G) es adyacente a exactamente una arista de M. Un perfect edge dominating set (PED-set) es un conjunto P de aristas tal que cada arista de E(G) \ P es adyacente a exactamente una arista de P. Nuestra atención estará en los problemas de decisión tanto para DIM como para PED, donde el primero pregunta por la existencia de un DIM de un grafo dado, y el segundo pregunta por un PED-set de tamaño a lo sumo k de un grafo dado. En una charla anterior se presentó una pincelada de un algoritmo cúbico que resuelve el problema PED en grafos P6-free. En esta ocasión, mostraremos algunas modificaciones hechas a este algoritmo para resolver el problema PED pesado y para contar el número de PED-sets en la clase P6-free, además de una breve resolución del problema DIM en grafos co-cordales.
Son todos bienvenidos y si están interesados en participar frecuentemente en este seminario, los invitamos a unirse a nuestro grupo de Telegram: https://t.me/+