A versão algorítmica do Lema Local de Lovász com aplicações a problemas de coloração de grafos
Carregando...
Data
Autor(es)
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Dissertação de mestrado
Título alternativo
Primeiro orientador
Membros da banca
Bhalchandra Digambar Thatte
Sokol Ndreca
Sokol Ndreca
Resumo
O objetivo deste trabalho é apresentar a demonstração da versão algorítmica do lema local de Lovász bem como uma versão melhorada do mesmo e aplicá-lo a problemas de coloração de grafos.
Abstract
The objective of this work is to present the proof of the algorithmic version of the Lovász local lema as well as an improved version of it and apply it to problems of coloring of graphs.
Assunto
Matemática
Palavras-chave
Lema Local de Lovász, Grafo de Dependência, Algoritmo