Please use this identifier to cite or link to this item:
http://repositorio.ufc.br/handle/riufc/50955| Type: | Dissertação |
| Title: | Coloração k-imprópria gulosa |
| Title in English: | Greedy k-improper coloring |
| Authors: | Rodrigues, Efraim Naassom Helem Dantas |
| Advisor: | Sales, Cláudia Linhares |
| Keywords: | Coloração gulosa;Coloração defectiva;Coloração imprópria;Árvores binomiais;Cografos;Programação matemática |
| Issue Date: | 2020 |
| Citation: | RODRIGUES, 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. |
| Abstract in Brazilian Portuguese: | Uma 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. |
| Abstract: | 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). |
| URI: | http://www.repositorio.ufc.br/handle/riufc/50955 |
| Appears in Collections: | DCOMP - Dissertações defendidas na UFC |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| 2020_dis_enhdrodrigues.pdf | 568,99 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.