============================================================
   Seminário de Teoria da Computação e Combinatória (TCC)

============================================================

Título:      Algoritmos locais: uma ponte entre resultados
             determinísticos e probabilísticos em grafos
            
Palestrante: Carlos Hoppen 
             Instituto de Matemática, UFRGS

Hora e Data: 14h, sexta-feira, 21 de fevereiro de 2014

Local:       Sala Multi-usos do Numec

Resumo:

A palestra  tratará de propriedades de  grafos regulares com
cintura grande  que podem ser obtidas através  da análise de
uma certa classe  de algoritmos. Por exemplo, consideraremos
conjuntos  independentes,  dominantes,  árvores induzidas  e
bipartições. Tais  resultados seguem de uma  relação entre a
performance de  algoritmos em grafos aleatórios  e em grafos
de cintura grande, de forma  que uma série de resultados são
derivados  diretamente  de  algoritmos  já  conhecidos  para
grafos   aleatórios  e   de   técnicas  desenvolvidas   para
analisá-los.

Trabalho em colaboração com Nick Wormald (Monash University,
Australia)