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

[Lucía Busolini]

¡Hola a todos!

Los invitamos a un nuevo encuentro del seminario de grafos, el próximo *lunes
20/04 a las 14 hs.* *en la sala de reuniones 2119 del Pabellón 0+infinito*.

*Expositor:* Eric Brandwein

*Título:* ¡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é parametros
> estructurales de G es que F-Deletion admite un kernel polinomial?


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/+RkVxwjjIdiE1Yjkx y visitar la página del seminario:
https://web.dm.uba.ar/index.php/investigacion/seminarios/seminario-grafos .

Cualquier duda o consulta pueden escribirnos.

¡Nos vemos pronto!

Saludos,
Lucía