[general_dat] Seminario de Grafos - Lunes 9/9 a las 14:30 hs

[Lucía Busolini]

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