Atenção: Todas as denúncias são sigilosas e sua identidade será preservada.
Os campos nome e e-mail são de preenchimento opcional
Metadados | Descrição | Idioma |
---|---|---|
Autor(es): dc.contributor | Almeida, Sheila Morais de | - |
Autor(es): dc.contributor | Almeida, Sheila Morais de | - |
Autor(es): dc.contributor | Alves, Gleifer Vaz | - |
Autor(es): dc.contributor | Queiroz, Saulo Jorge Beltrao de | - |
Autor(es): dc.contributor | Maciel, Denise do Rocio | - |
Autor(es): dc.creator | Becher, Gabriel Coplas | - |
Data de aceite: dc.date.accessioned | 2022-02-21T21:41:30Z | - |
Data de disponibilização: dc.date.available | 2022-02-21T21:41:30Z | - |
Data de envio: dc.date.issued | 2020-11-18 | - |
Data de envio: dc.date.issued | 2020-11-18 | - |
Data de envio: dc.date.issued | 2019-06-26 | - |
Fonte completa do material: dc.identifier | http://repositorio.utfpr.edu.br/jspui/handle/1/16000 | - |
Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/capes/658375 | - |
Descrição: dc.description | A 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.description | Uma 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.format | application/pdf | - |
Idioma: dc.language | pt_BR | - |
Publicador: dc.publisher | Universidade Tecnológica Federal do Paraná | - |
Publicador: dc.publisher | Ponta Grossa | - |
Publicador: dc.publisher | Brasil | - |
Publicador: dc.publisher | Departamento Acadêmico de Informática | - |
Publicador: dc.publisher | Ciência da Computação | - |
Publicador: dc.publisher | UTFPR | - |
Direitos: dc.rights | openAccess | - |
Palavras-chave: dc.subject | Representações dos grafos | - |
Palavras-chave: dc.subject | Cor - Percepção | - |
Palavras-chave: dc.subject | Análise de sistemas | - |
Palavras-chave: dc.subject | Algorítmos | - |
Palavras-chave: dc.subject | Representations of graphs | - |
Palavras-chave: dc.subject | Color vision | - |
Palavras-chave: dc.subject | System analysis | - |
Palavras-chave: dc.subject | Algorithms | - |
Palavras-chave: dc.subject | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO | - |
Título: dc.title | Coloração total de grafos bipartidos | - |
Título: dc.title | Total coloring of bipartite graphs | - |
Tipo de arquivo: dc.type | livro digital | - |
Aparece nas coleções: | Repositorio Institucional da UTFPR - RIUT |
O Portal eduCAPES é oferecido ao usuário, condicionado à aceitação dos termos, condições e avisos contidos aqui e sem modificações. A CAPES poderá modificar o conteúdo ou formato deste site ou acabar com a sua operação ou suas ferramentas a seu critério único e sem aviso prévio. Ao acessar este portal, você, usuário pessoa física ou jurídica, se declara compreender e aceitar as condições aqui estabelecidas, da seguinte forma: