[general_dat] Seminario de Grafos - Lunes 20/4 a las 14 hs

[Aye Alcantar]

Buen viernes gente!!

Les dejamos la información de la próxima charla. La misma estará a cargo de
Eric Brandwein quien presentará el Lunes *20 de abril* a las *14hs,* en la
sala *2119 del Pabellón 0+infinito,* el trabajo titulado: "*¡Rápido,
péguenles a esos (grafos) menores!"*

*Resumen: *El problema de Vertex Cover consiste en eliminar la mínima
> cantidad de vértices de un grafo G tal que no quede ninguna arista.
> "Pegarles" a estas aristas con vértices de G se puede ver como eliminar
> todas las copias de un grafo H en G, donde H es solo dos vértices
> conectados por una arista. Esta idea se puede generalizar a cualquier grafo
> H.

Además, podríamos querer pegarle a H no en términos de subgrafos, pero en
> términos de menores. Un menor de un grafo G es el resultado de eliminar
> algunos vértices, eliminar algunas aristas, y contraer otras aristas de G.

   Esta charla se centra en el problema general de F-Deletion, que consiste
> en encontrar la mínima cantidad de vértices a eliminar para pegarle a todos
> los menores de una familia F. Como estos problemas son casi todos NP-hard,
> nos restringimos a resolverlos cuando el grafo de entrada cumple algunas
> propiedades particulares. Incluso nos preguntamos: ¿qué propiedades
> particulares tiene que cumplir el grafo para que efectivamente se pueda
> resolver F-Deletion rápidamente? En específico, y para los entendidos (lo
> vamos a explicar en la charla, no se preocupen), ¿para qué parámetros
> estructurales de G es que F-Deletion admite un kernel polinomial?


Como siempre, les dejamos el link a nuestro grupo de Telegram
<https://t.me/+RkVxwjjIdiE1Yjkx> y nuestra  Web del seminario
<https://web.dm.uba.ar/index.php/investigacion/seminarios/seminario-grafos>
para que pasen a visitar.

Esperamos que tengan un buen fin de semana, nos vemos el lunes!!

Saludos,
-- 
Aye Alcantar