Propriedades de grafos com cintura grande

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).