[general_dat] Seminario de Grafos - Lunes 1/6 a las 14 hs

[Lucía Busolini]

¡Hola a todos!

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

*Expositor:* Ignacio Maqueda

*Título:* One Gate to Rule Them All Out: Propagación en clases hereditarias
de grafos

*Resumen:*

> Muchas clases de grafos se describen prohibiendo ciertos subgrafos
> inducidos. Sin embargo, contar con una caracterización estructural no
> siempre implica tener un algoritmo eficiente para reconocer cuándo un grafo
> pertenece a la clase.

En esta charla presentamos un enfoque general para abordar este problema
> usando sistemas lineales asociados al conteo de subgrafos inducidos. La
> idea central es elegir un subgrafo distinguido, al que llamamos *gate*,
> cuya ausencia pueda verificarse eficientemente. Luego, podemos usar esa
> información para propagar restricciones que certifiquen la ausencia de
> otras configuraciones prohibidas.

Veremos que este enfoque da lugar a distintos comportamientos algorítmicos:
> en algunos casos alcanza para reconocer completamente la clase, mientras
> que en otras reduce el problema a detectar una única obstrucción residual o
> incluso a resolver un problema estructural más simple, como testear si un
> grafo es o no bipartito.


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!

Saludos,
Lucía