Coloração k-imprópria gulosa

Detalhes bibliográficos
Ano de defesa: 2020
Autor(a) principal: Rodrigues, Efraim Naassom Helem Dantas
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Não Informado pela instituição
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: http://www.repositorio.ufc.br/handle/riufc/50955
Resumo: A vertex coloring of a graph G= (V,E) is proper if adjacent vertices have distinct colors. In this work, we study a relaxation of this problem, called k-improper coloring, in which, given a positive integer k, each vertex can share its color with at most k neighbors. Since the proper coloring problem is a 0-improper coloring, this relaxation is as difficult as the classic coloring problem, and thus it can be approached by the means of heuristics. Here, we introduce the k-improper version of the greedy coloring heuristic. As usual, we aim to estimate the worst case of this heuristic. Besides introducing the k-improper Grundy Number, we generalized the concept of t-atoms as well as we investigated the k-improper Grundy Number for binomial trees and cographs, and presented mathematical programming formulations for the improper and proper Grundy Number (fulfilling a gap in this study).