[general_dat] Seminario de Grafos - SUSPENDIDO

[Lucía Busolini]

Buenos días!

Les quería avisar que *se suspende el seminario de hoy*. Nos encontraremos
nuevamente el lunes 23/9, más cerca de esa fecha mandaremos la invitación.

Que tengan una linda semana!

Saludos,
Lucía

El vie, 6 sept 2024 a las 17:02, Lucía Busolini (<lucia.busolini at gmail.com>)
escribió:

> Buenas tardes!
>
> Queremos invitarlos a participar de un nuevo encuentro
> del Seminario de Grafos. La próxima charla será el* lunes 9/9 a las 14:30
> hs.* en la *sala de reuniones 2119 del Pabellón 0+infinito*.
> Recuerden que también pueden sumarse a nuestro grupo de Telegram:
> https://t.me/+RkVxwjjIdiE1Yjkx
>
> Ahora sí, la información sobre la charla:
>
> *Expositora:* Flavia Bonomo
> *Título:* Thinness de grafos y otros parámetros de ancho. Parte II:
> resultados estructurales.
>
> *Resumen*:
>
>> Gran parte de los problemas de optimización definidos sobre grafos son
>> computacionalmente difíciles. Para estos problemas, resulta natural
>> preguntarse: ¿Para qué subclases de grafos el problema puede resolverse de
>> forma eficiente y para cuáles es intrínsecamente difícil?
>>
>> Además de la detección de clases particulares y algoritmos ad-hoc para
>> esas clases, desde los años '80, varios "parámetros de ancho" en un grafo
>> fueron definidos, con el objetivo de abarcar clases de grafos dentro de las
>> cuales problemas NP-completos en general resultaran polinomiales. El
>> primero y más conocido es el treewidth, que mide qué tanto se parece en
>> estructura a un árbol (los árboles son exactamente los grafos de treewidth
>> 1). Saber que una familia de grafos tiene un parámetro de ancho acotado
>> permite diseñar algoritmos eficientes, en general utilizando programación
>> dinámica, para muchos problemas famosos, como el problema de coloreo de
>> grafos o el de conjunto independiente máximo, y versiones más generales de
>> ellos. Más aún, en muchos casos se lograron resultados algorítmicos de
>> aplicación muy general, conocidos como "metateoremas". Un metateorema tiene
>> la forma: "si un problema puede ser expresado en tal lenguaje o con este
>> tipo de restricciones: [tipo correspondiente], entonces puede ser resuelto
>> en tiempo polinomial para grafos de [ancho correspondiente] acotado". Estos
>> temas forman parte de las áreas de complejidad parametrizada y algoritmos
>> parametrizados.
>>
>> Los parámetros de ancho en los que estamos trabajando últimamente son la
>> thinness y sus variantes. La thinness fue definida por Mannino, Oriolo,
>> Ricci y Chandran en 2007 en el marco de una aplicación a problemas
>> provenientes de la telefonía celular vinculados con el problema de conjunto
>> independiente en grafos, y mide qué tanto se parece un grafo en estructura
>> a un grafo de intervalos (que son exactamente los grafos de thinness 1).
>>
>> En esta serie de charlas presentaremos los principales resultados
>> conocidos sobre la thinness de un grafo, incluyendo un metateorema para la
>> thinness y algunos resultados muy recientes de trabajos en curso, y las
>> preguntas abiertas en las que planeamos trabajar en los próximos años.
>>
>
> Están todos invitados, cualquier duda pueden escribirme. Nos vemos!
>
> Saludos!
> Lucía Busolini
>