Coloração total de grafos bipartidos

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorAlmeida, Sheila Morais de-
Autor(es): dc.contributorAlmeida, Sheila Morais de-
Autor(es): dc.contributorAlves, Gleifer Vaz-
Autor(es): dc.contributorQueiroz, Saulo Jorge Beltrao de-
Autor(es): dc.contributorMaciel, Denise do Rocio-
Autor(es): dc.creatorBecher, Gabriel Coplas-
Data de aceite: dc.date.accessioned2022-02-21T21:41:30Z-
Data de disponibilização: dc.date.available2022-02-21T21:41:30Z-
Data de envio: dc.date.issued2020-11-18-
Data de envio: dc.date.issued2020-11-18-
Data de envio: dc.date.issued2019-06-26-
Fonte completa do material: dc.identifierhttp://repositorio.utfpr.edu.br/jspui/handle/1/16000-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/658375-
Descrição: dc.descriptionA total coloring in a graph G is a color assignment to elements to G so that any two adjacent elements have different colors. The Total Coloring Problem is to determine the smallest number of colors to obtain a total coloring for a given graph G. This number is called the total chromatic number and it is denoted by X"(G). In its decision version, the Total Coloring Problem receives as input a graph G and an integer number, k, and it is desired to know if there is a total coloring for G with at most k colors. The decision version of Total Coloring Problem is an NP - Complete problem, even when restricted to the class of bipartite graphs, which are those whose vertices can be partitioned into two independent sets. An efficient algorithm that solves any of the NP-Complete problems in polynomial time is unknown, but if any algorithm of polynomial complexity exists, then it can be used to solve any problem of the class NP. Presenting an efficient algorithm for an NP - complete problem or proving that such an algorithm does not exist is one of the seven most challenging problems of the millennium, according to the Clay Mathematics Institute. In this work we present a subset of bipartite graphs for which the Total Coloring Problem remains open.-
Descrição: dc.descriptionUma coloração total em um grafo G é uma atribuição de cores para os elementos de G de forma que quaisquer dois elementos adjacentes tenham cores diferentes. O Problema da Coloração Total é determinar o menor número de cores com que se pode obter uma coloração total de um dado grafo G. Esse número é denominado de número cromático total e denotado por X"(G). Em sua versão de decisão, o Problema da Coloração Total recebe como entrada um grafo G e um número inteiro k para os quais deseja-se saber se é possível realizar uma coloração total de G com no máximo k cores. A versão de decisão do Problema da Coloração Total é um problema NP - completo mesmo quando restrita à classe dos grafos bipartidos, que são aqueles cujos vértices podem ser particionados em dois conjuntos independentes. Não se conhece algoritmo eficiente que resolva em tempo polinomial qualquer dos problemas NP - completos, mas caso algum algoritmo de complexidade polinomial exista, então o mesmo poderá ser utilizado para resolver qualquer problema da classe de problemas NP. Apresentar um algoritmo eficiente para um problema NP - completo ou provar que tal algoritmo não existe é um dos sete problemas mais desafiadores do milênio, segundo o Clay Mathematics Institute. Nesse trabalho determinou-se um subconjunto dos grafos bipartidos em que o Problema da Coloração Total permanece em aberto.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Publicador: dc.publisherUniversidade Tecnológica Federal do Paraná-
Publicador: dc.publisherPonta Grossa-
Publicador: dc.publisherBrasil-
Publicador: dc.publisherDepartamento Acadêmico de Informática-
Publicador: dc.publisherCiência da Computação-
Publicador: dc.publisherUTFPR-
Direitos: dc.rightsopenAccess-
Palavras-chave: dc.subjectRepresentações dos grafos-
Palavras-chave: dc.subjectCor - Percepção-
Palavras-chave: dc.subjectAnálise de sistemas-
Palavras-chave: dc.subjectAlgorítmos-
Palavras-chave: dc.subjectRepresentations of graphs-
Palavras-chave: dc.subjectColor vision-
Palavras-chave: dc.subjectSystem analysis-
Palavras-chave: dc.subjectAlgorithms-
Palavras-chave: dc.subjectCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO-
Título: dc.titleColoração total de grafos bipartidos-
Título: dc.titleTotal coloring of bipartite graphs-
Tipo de arquivo: dc.typelivro digital-
Aparece nas coleções:Repositorio Institucional da UTFPR - RIUT

Não existem arquivos associados a este item.