<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META http-equiv=Content-Type content="text/html; charset=iso-8859-1">
<META content="MSHTML 6.00.6000.16674" name=GENERATOR></HEAD>
<BODY>
<DIV>
<P><FONT face=Arial size=2>Quién: Marcelo Mydlarz</FONT></P>
<P><FONT face=Arial size=2>Título: Un algoritmo rápido para coloreo
equilibrado</FONT></P>
<P><FONT face=Arial size=2>Abstract:</FONT></P>
<P><FONT face=Arial size=2>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<SPAN class=296492618-23062008>é</SPAN>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.</FONT></P>
<P><FONT face=Arial size=2>Trabajo en colaboración con H. Kierstead, A.
Kostochka y E. Szemer<SPAN class=296492618-23062008>é</SPAN>di</FONT></P>
<P><FONT face=Arial size=2>Bio: Marcelo es Licenciado en Ciencias de la
Computación del Depto<SPAN class=296492618-23062008>.</SPAN> 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.<SPAN
class=296492618-23062008> </SPAN>Trabajó en diversar áreas como algoritmos
online, programación entera, multicommodity flows y teoría de grafos.
Actualmente trabaja en Yahoo!<SPAN class=296492618-23062008> </SPAN>Research en
subastas online, búsqueda y web crawling .</FONT></P>
<P><FONT face=Arial size=2>Cuándo: Viernes 27/6/08, 18:30 horas</FONT></P>
<P><FONT face=Arial><FONT size=2>Dónde: Aula <SPAN
class=296492618-23062008>3 - Pabellón I</SPAN></FONT></FONT></P>
<P><FONT face=Arial size=2></FONT> </P></DIV></BODY></HTML>