[general_dat] Seminario de Grafos - Lunes 19/10 a las 14 hs

[Lucía Busolini]

Buenos tardes!

Escribo para invitarlos al próximo encuentro del seminario de grafos que
será el* lunes 19/10 a las 14 hs. en la sala de reuniones 2119 del Pabellón
0+infinito*.

*Oradores:* Ignacio Lucas Rodriguez y Mauricio Romero Laino

*Título:* Plegabilidad: un nuevo parámetro de ancho

*Resumen:*

> Muchos de los problemas en grafos que buscamos resolver son NP-completos
> en general. Sin embargo, esto no significa que debamos rendirnos. Al
> restringir la clase de grafos, es posible aprovechar su estructura para
> diseñar algoritmos eficientes. Una forma clásica de lograrlo es mediante
> parámetros de ancho, que miden cuán lejos está un grafo de tener una
> estructura simple.

En esta charla presentamos un nuevo parámetro de ancho, que llamamos
> provisoriamente plegabilidad. Un grafo es k-plegable si existe un orden de
> sus vértices y una partición de los mismos en k clases tal que, para toda
> arista vw con v < w, ningún vértice u ubicado entre v y w pertenece a la
> misma clase que v ni a la misma clase que w. Los grafos 1-plegables son
> exactamente los bosques lineales, por lo que la plegabilidad puede pensarse
> como una medida de la distancia a esta clase.

Estudiamos la complejidad de problemas relacionados con la plegabilidad, la
> relacionamos con otros parámetros conocidos. Luego caracterizamos la
> estructura de los grafos 2-plegables, los cuales tienen una estructura muy
> particular. Finalmente, discutimos el comportamiento de la plegabilidad
> frente a subdivisiones y supresiones de vértices, y las preguntas abiertas
> para plegabilidades mayores.


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
Para quienes no puedan estar presencialmente, también está la oportunidad
de participar virtualmente, pasaremos el link de Meet por el grupo de
Telegram.

Cualquier duda o consulta pueden escribirnos.

¡Nos vemos!

Saludos,
Lucía