[general_dat] Seminario de Grafos - Lunes 14/10 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 14/10 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:

*Expositor:* Oscar Lin
*Título:* Un algoritmo robusto, eficiente con certificado para resolver el
problema de clique máximo pesado en grafos monopolares

*Resumen:*

> Un grafo G=(V,E) es monopolar si sus vértices se puede particionar en 2
> subconjuntos A y B de manera tal que A es un conjunto independiente y G[B]
> el subgrafo inducido por B es un grafo cluster (equivalentemente grafo
> P_3-free). El problema de reconocer esta clase de grafos es NP-Completo. El
> problema de encontrar un clique de peso máximo se puede resolver en tiempo
> polinomial para un grafo monopolar tanto para (i) el caso donde se conoce
> la partición (A,B) de antemano  como para (ii) no se  conoce tal partición.
> Para (i) existe un algoritmo lineal (O(n+m), siendo n=|V| y m=|E|) y para
> (ii) hay un algoritmo de tiempo O(mn^2+nm^2) con un grafo monopolar como
> entrada. En esta charla, vamos a dar un algoritmo robusto de tiempo
> O(a(G)m) que trata de resolver el problema de clique de peso máximo para un
> grafo (monopolar o no) y puede generar 2 posibles resultados: (I) resuelve
> el problema satisfactoriamente para el grafo de entrada sin saber si es
> monopolar o no (II) devolver un certificado (evidencia) de tamaño O(1) que
> el grafo de entrada no es monopolar.


Están todos invitados, cualquier duda pueden escribirme. Nos vemos!

Saludos!
Lucía Busolini