Coloração de Grafos(r,l)

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorSouza, Uéverton dos Santos-
Autor(es): dc.contributorBravo, Raquel-
Autor(es): dc.contributorNogueira, Loana Tito-
Autor(es): dc.creatorAlves, Matheus Souza D'Andrea-
Data de aceite: dc.date.accessioned2024-07-11T17:31:38Z-
Data de disponibilização: dc.date.available2024-07-11T17:31:38Z-
Data de envio: dc.date.issued2023-09-26-
Data de envio: dc.date.issued2023-09-26-
Fonte completa do material: dc.identifierhttp://app.uff.br/riuff/handle/1/30595-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/752107-
Descrição: dc.descriptionUm problema clássico na literatura é o problema de coloração própria de um grafo, isto é, encontrar uma q − coloração para um grafo G tal que todo vértice v ∈ V (G) não possua nenhum vizinho da mesma cor e q seja mínimo. Esse problema é conhecido ser NP-Difícil para grafos gerais. O trabalho a seguir tem como proposta desvendar e catalogar a complexidade clássica e parametrizada de tal problema para a classe de Grafos(r, `), i.e. grafos particionáveis em r conjuntos independentes e l cliques; Identificando as características que tornam o problema difícil e a relação do problema de coloração com outros problemas, quando abordado pela perspectiva parametrizada-
Descrição: dc.descriptionA classical problem in graph theory is the problem of proper coloring a graph, i.e. to find a q − coloring for a graph G such that every vertex v ∈ V (G) does not have any neighbor of the same color and q is the smallest possible number, a problem known to be NP-Hard for a general graphs. The following work attempts to uncover and catalog the parametrized complexity of such problem for the class of graphs(r, l), i.e. partitionable graphs in r independent sets and l cliques; Identifying the characteristics that make the problem hard and the relation of the stated problem to other problems when approached by the parameterized perspective-
Descrição: dc.description35 p.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Direitos: dc.rightsOpen Access-
Direitos: dc.rightsCC-BY-SA-
Palavras-chave: dc.subjectComplexidade parametrizada-
Palavras-chave: dc.subjectGrafos(r, l)-
Palavras-chave: dc.subjectPartição de grafos-
Palavras-chave: dc.subjectColoração de grafos-
Palavras-chave: dc.subjectGrafo-
Palavras-chave: dc.subjectComplexidade parametrizada-
Palavras-chave: dc.subjectColoração de grafos-
Palavras-chave: dc.subjectParametrized Complexity-
Palavras-chave: dc.subjectGraph(r, l)-
Palavras-chave: dc.subjectGraph Partitioning-
Palavras-chave: dc.subjectGraph Coloring-
Título: dc.titleColoração de Grafos(r,l)-
Tipo de arquivo: dc.typeTrabalho de conclusão de curso-
Aparece nas coleções:Repositório Institucional da Universidade Federal Fluminense - RiUFF

Não existem arquivos associados a este item.