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 | Maciel, Denise do Rocio | - |
Autor(es): dc.contributor | Almeida, Sheila Morais de | - |
Autor(es): dc.contributor | Maciel, Denise do Rocio | - |
Autor(es): dc.contributor | Siqueira, Hugo Valadares | - |
Autor(es): dc.contributor | Zatesko, Leandro Miranda | - |
Autor(es): dc.creator | Barchi, Tathiana Mikamura | - |
Data de aceite: dc.date.accessioned | 2022-02-21T21:42:07Z | - |
Data de disponibilização: dc.date.available | 2022-02-21T21:42:07Z | - |
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-12-02 | - |
Fonte completa do material: dc.identifier | http://repositorio.utfpr.edu.br/jspui/handle/1/16009 | - |
Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/capes/658619 | - |
Descrição: dc.description | The Vertex Coloring Problem remains open for circular-arc graphs. Moreover, it is known that the decision version of this problem isNP-complete even when restricted to this class. However, there are efficient algorithms for some subclasses such as proper circular-arc graphs and perfect circular-arc graphs. In this work, two polynomial time vertex coloring techniques are studied: Greedy Algorithm and Pair-contracting Operation. Althought there are cases in which the vertex coloring presented by these techniques are not optimal, they can be successfully used on chordal graphs. We modify these techniques to efficiently color a subset of the circular-arc graphs which are not perfect and not proper. | - |
Descrição: dc.description | O Problema da Coloração de Vértices permanece em aberto para a classe dos grafos arcocirculares. Além disso, sabe-se que a versão de decisão deste problema é NP-completa mesmo quando restrita a esta classe. Apesar disso, existem algoritmos eficientes para algumas subclasses, como arco-circulares próprios e arco-circulares perfeitos. Nesse trabalho foram estudadas duas técnicas com complexidade de tempo polinomial para a coloração de vértices: Algoritmo Guloso e Contração de Dupla de Vértices. Embora estas técnicas nem sempre resultem em uma coloração de vértices ótima, podem ser aplicadas com sucesso em grafos cordais. Modificamos estas técnicas para colorir de forma eficiente um subconjunto de grafos arco-circulares que não são perfeitos e não são próprios. | - |
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 | Cores | - |
Palavras-chave: dc.subject | Grafos de ligação | - |
Palavras-chave: dc.subject | Algorítmos | - |
Palavras-chave: dc.subject | Colors | - |
Palavras-chave: dc.subject | Bond graphs | - |
Palavras-chave: dc.subject | Algorithms | - |
Palavras-chave: dc.subject | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO | - |
Título: dc.title | Coloração de vértices em grafos arco-circulares | - |
Título: dc.title | Vertex coloring on circular-arc 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: