[general_dat] Seminario de Grafos - Lunes 24/8 a las 14 hs

[Lucía Busolini]

¡Hola a todos!

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

*Oradora:* Yo

*Título:* Reconfiguración de Conjuntos Independientes en grafos con pocos P4

*Resumen:*

> Consideramos el problema de RECONFIGURACIÓN DE CONJUNTOS INDEPENDIENTES
> bajo la regla de Token Sliding. Sea I un conjunto independiente de un grafo
> G. Supongamos que cada vértice de I tiene una ficha colocada sobre él. Las
> fichas pueden moverse, una a la vez, deslizándolas a lo largo de las
> aristas de G, de manera que, después de cada movimiento, los vértices que
> contienen fichas sigan formando siempre un conjunto independiente de G.
>
> El problema que abordamos consiste en decidir si es posible transformar
> I en I' mediante una secuencia de pasos, cada uno de los cuales implica
> sustituir un vértice del conjunto independiente actual por uno de sus
> vecinos para obtener otro conjunto independiente. Este problema de
> determinar si un conjunto independiente de un grafo es “alcanzable” desde
> otro conjunto independiente del mismo grafo se sabe que es PSPACE-difícil,
> incluso para grafos split, grafos perfectos y grafos treewidth acotada.
>
> Se han obtenido algoritmos polinomiales para ciertas clases de grafos,
> como árboles, grafos de intervalos, grafos claw-free, grafos de permutación
> bipartitos, grafos bloque y cografos. Presentamos un algoritmo de tiempo
> polinomial para este problema en grafos P4-tidy y grafos (q, q-4), dos
> familias de grafos que generalizan a los cografos.
>

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