[Todos] Recordatorio - Charla en el DC: Un algoritmo rápido para coloreo equilibrado
efeuerst en dc.uba.ar
efeuerst en dc.uba.ar
Jue Jun 26 10:58:35 ART 2008
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
Más información sobre la lista de distribución Todos