Use este identificador para citar ou linkar para este item: http://repositorio.ufc.br/handle/riufc/50955
Registro completo de metadados
Campo DCValorIdioma
dc.contributor.advisorSales, Cláudia Linhares-
dc.contributor.authorRodrigues, Efraim Naassom Helem Dantas-
dc.date.accessioned2020-03-27T12:40:44Z-
dc.date.available2020-03-27T12:40:44Z-
dc.date.issued2020-
dc.identifier.citationRODRIGUES, Efraim Naassom Helem Dantas. Coloração k-imprópria gulosa. 2020. 61 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal do Ceará, Fortaleza, 2020.pt_BR
dc.identifier.urihttp://www.repositorio.ufc.br/handle/riufc/50955-
dc.description.abstractA 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).pt_BR
dc.language.isopt_BRpt_BR
dc.subjectColoração gulosapt_BR
dc.subjectColoração defectivapt_BR
dc.subjectColoração imprópriapt_BR
dc.subjectÁrvores binomiaispt_BR
dc.subjectCografospt_BR
dc.subjectProgramação matemáticapt_BR
dc.titleColoração k-imprópria gulosapt_BR
dc.typeDissertaçãopt_BR
dc.description.abstract-ptbrUma coloração dos vértices de um grafo G= (V,E) é própria se vértices adjacentes recebem cores diferentes. Estudamos neste trabalho uma relaxação desse problema, chamada de coloração k-imprópria, onde, dado um inteiro positivo k, a cor de um vértice qualquer pode ser compartilhada com até k de seus vizinhos. Uma vez que a coloração própria é uma coloração 0-imprópria, a coloração k-imprópria é igualmente um problema difícil, podendo-se, analogamente, abordar o problema através do uso de heurísticas. Neste trabalho, introduzimos a versão k-imprópria da heurística de coloração gulosa de grafos. Como se faz habitualmente, o estudo aqui almejava estimar o pior desempenho dessa heurística. Além de introduzir o conceito de Número de Grundy k-impróprio, generalizamos o conceito de t-átomo, estudamos o parâmetro em árvores binomiais e cografos, e apresentamos formulações de programação por restrições e programação inteira,não apenas para a coloração gulosa imprópria, mas também para o Número de Grundy clássico, preenchendo um vácuo naquele estudo.pt_BR
dc.title.enGreedy k-improper coloringpt_BR
Aparece nas coleções:DCOMP - Dissertações defendidas na UFC

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
2020_dis_enhdrodrigues.pdf568,99 kBAdobe PDFVisualizar/Abrir
Mostrar registro simples do item Visualizar estatísticas


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.