Carlos Hoppen
Posdoc do DCC-IME-USP
Sexta-feira, 7 de março de 2008, 14:00
Anfiteatro do NUMEC-USP
Resumo:
Essa palestra destina-se à apresentação de uma classe de algoritmos probabilísticos em grafos. Analisando a performance de tais algoritmos em grafos de cintura grande, obtemos cotas relacionadas com problemas clássicos em Teoria dos Grafos, como a cardinalidade de um conjunto independente máximo e o número de vértices em uma floresta induzida máxima, entre outros. A relação dessas cotas com grafos aleatórios regulares também será mencionada.
Trata-se de um trabalho conjunto com Nick Wormald (University of Waterloo).