[Todos] Charla en el DC: Un algoritmo rápido para coloreo equilibrado

[Esteban Feuerstein]

Quién: Marcelo Mydlarz

Título: Un algoritmo rápido para coloreo equilibrado

Abstract:

Llamamos al coloreo de los vértices de un grafo equilibrado si el tamaño de
cada clase coloreada difiere en a lo sumo uno. El famoso teorema de
Hajnal-Szemerédi dice: para todo entero positivo $r$, todo grafo con grado
máximo a lo sumo $r$ tiene un coloreo equilibrado con $r+1$ colores.
Presentaré una demostración constructiva de este teorema, que da lugar a un
algoritmo polinomial.

Trabajo en colaboración con H. Kierstead, A. Kostochka y E. Szemerédi

Bio: Marcelo es Licenciado en Ciencias de la Computación del Depto. de
Computación - FCEyN - UBA. Obtuvo el Marster y el Ph.D. en Investigación
Operativa de la Universidad de Rutgers en 2003 y 2006 respectivamente.
Trabajó en diversar áreas como algoritmos online, programación entera,
multicommodity flows y teoría de grafos. Actualmente trabaja en Yahoo!
Research en subastas online, búsqueda y web crawling .

Cuándo: Viernes 27/6/08, 18:30 horas

Dónde: Aula 3 - Pabellón I

 

------------ próxima parte ------------
Se ha borrado un adjunto en formato HTML...
URL: http://mail.df.uba.ar/pipermail/todos/attachments/20080623/9d71f570/attachment.html