Atenção:
O eduCAPES é um repositório de objetos educacionais, não sendo responsável por materiais de terceiros submetidos na plataforma. O usuário assume ampla e total responsabilidade quanto à originalidade, à titularidade e ao conteúdo, citações de obras consultadas, referências e outros elementos que fazem parte do material que deseja submeter. Recomendamos que se reporte diretamente ao(s) autor(es), indicando qual parte do material foi considerada imprópria (cite página e parágrafo) e justificando sua denúncia.
Caso seja o autor original de algum material publicado indevidamente ou sem autorização, será necessário que se identifique informando nome completo, CPF e data de nascimento. Caso possua uma decisão judicial para retirada do material, solicitamos que informe o link de acesso ao documento, bem como quaisquer dados necessários ao acesso, no campo abaixo.
Todas as denúncias são sigilosas e sua identidade será preservada. Os campos nome e e-mail são de preenchimento opcional. Porém, ao deixar de informar seu e-mail, um possível retorno será inviabilizado e/ou sua denúncia poderá ser desconsiderada no caso de necessitar de informações complementares.
Metadados | Descrição | Idioma |
---|---|---|
Autor(es): dc.contributor | Silva, Murilo Vicente Gonçalves da | - |
Autor(es): dc.contributor | Zatesko, Leandro Miranda, 1988- | - |
Autor(es): dc.contributor | Universidade Federal do Paraná. Setor de Ciências Exatas. Programa de Pós-Graduação em Informática | - |
Autor(es): dc.creator | Bernardi, João Pedro Winckler | - |
Data de aceite: dc.date.accessioned | 2020-09-24T17:28:45Z | - |
Data de disponibilização: dc.date.available | 2020-09-24T17:28:45Z | - |
Data de envio: dc.date.issued | 2020-07-31 | - |
Data de envio: dc.date.issued | 2020-07-31 | - |
Data de envio: dc.date.issued | 2019 | - |
Fonte completa do material: dc.identifier | https://hdl.handle.net/1884/67798 | - |
Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/1884/67798 | - |
Descrição: dc.description | Orientador: Murilo V. G. da Silva | - |
Descrição: dc.description | Coorientador: Leandro M. Zatesko | - |
Descrição: dc.description | Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa : Curitiba, 17/03/2020 | - |
Descrição: dc.description | Inclui referências: p. 31-32 | - |
Descrição: dc.description | Área de concentração: Ciência da Computação | - |
Descrição: dc.description | Resumo: A famosa tabela de problemas NP-completos de D. Johnson de 1985 relaciona problemas NP-completos com classes de grafos. Uma entrada da tabela representa a complexidade de um problema para determinada classe de grafo. Desde que foi feita pela primeira vez, a entrada para o Problema de Coloração de Arestas com a classe dos grafos cordais permanece vazia, pois ainda é um problema indeterminado. Uma conjectura de Figueiredo, Meidanis, e Mello da década de 90 diz que todo grafo cordal com grau máximo ímpar tem seu índice cromático igual ao grau máximo do grafo. Com o estudo do problema, foi desenvolvida a técnica pullback para colorir um subconjunto os grafos de intervalos, uma subclasse dos grafos cordais. Nosso trabalho generaliza a pullback para colorir um subconjunto dos grafos arco-circulares próprios ? cordais, uma superclasse dos grafos de intervalos próprios. Palavras-chave: Pullback. Coloração de arestas. Coloração total. | - |
Descrição: dc.description | Abstract: Each entry from the famous D. Johnson's NP-completeness column of 1985 represents the complexity of a problem for a given graph class. Since it was first made, the entry for the Edge Coloring Problem with chordal graphs remains empty, as it is still undetermined. A conjecture by Figueiredo, Meidanis, and Mello, open since late 1990s, states that every chordal graph with odd maximum degree has its chromatic index equal to the maximum degree of the graph. With the study of the problem, the technique pullback was developed to color a subset of interval graphs, a subclass of chordal graphs. Our work generalizes the pullback to color a subset of proper circular arc ? chordals graphs, a superclass of the proper interval graphs. Keywords: Pullback. Edge-coloring. Total coloring. | - |
Formato: dc.format | 32 p. : il. (algumas color.). | - |
Formato: dc.format | application/pdf | - |
Formato: dc.format | application/pdf | - |
Palavras-chave: dc.subject | Homomorfismos (Matemática) | - |
Palavras-chave: dc.subject | Álgebra homológica | - |
Palavras-chave: dc.subject | Ciência da Computação | - |
Título: dc.title | Homomorfismos para coloração de grafos | - |
Aparece nas coleções: | Repositório Institucional - Rede Paraná Acervo |
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: