Use este identificador para citar ou linkar para este item:
http://repositorio.utfpr.edu.br/jspui/handle/1/15977
Registro completo de metadados
Campo DC | Valor | Idioma |
---|---|---|
dc.creator | D’Almeida, Diego Gonzales | |
dc.date.accessioned | 2020-11-19T18:24:30Z | - |
dc.date.available | 2020-11-19T18:24:30Z | - |
dc.date.issued | 2018-11-20 | |
dc.identifier.citation | D’ALMEIDA, Diego Gonzales. Coloração arco-íris para cografos. 2018. 40 f. Trabalho de Conclusão de Curso (Ciência da Computação) - Universidade Tecnológica Federal do Paraná, Ponta Grossa, 2018. | pt_BR |
dc.identifier.uri | http://repositorio.utfpr.edu.br/jspui/handle/1/15977 | - |
dc.description.abstract | An edge coloring of a graph is a assignment of colors to the edges of the graph. The rainbow coloring is an assignment of these colors such that for every pair of vertices there is a path that does not repeat colors. These paths are called rainbow paths. The Rainbow Coloring Problem consists in determining the least number of colors for a rainbow coloring of a given graph. This minimum number of colors is known as rainbow connection number and it is denotes by rc(G) for a graph G. The rainbow coloring Problem is NP-complete. There are efficient algorithms to solve it for few classes of graphs. This work presents a tight upper bound for the rainbow connection number of cographs, which are graphs without induced Ρ4. | pt_BR |
dc.language | por | pt_BR |
dc.publisher | Universidade Tecnológica Federal do Paraná | pt_BR |
dc.rights | openAccess | pt_BR |
dc.subject | Cores | pt_BR |
dc.subject | Grafos de ligação | pt_BR |
dc.subject | Arco-íris | pt_BR |
dc.subject | Colors | pt_BR |
dc.subject | Bond graphs | pt_BR |
dc.subject | Rainbow | pt_BR |
dc.title | Coloração arco-íris para cografos | pt_BR |
dc.title.alternative | Rainbow coloring for cographs | pt_BR |
dc.type | bachelorThesis | pt_BR |
dc.description.resumo | Uma coloração de arestas consiste na atribuição de cores às arestas do grafo. Uma forma de atribuição para essas cores é a coloração arco-íris. Essa coloração tem por característica a existência de um caminho que não repete cores entre cada par dos vértices do grafo - chamado de caminho arco-íris. O Problema da Coloração Arco-Íris consiste em encontrar o menor número de cores k para qual um grafo G possui uma coloração arco-íris. Esse k mínimo é chamado de número de conexão arco-íris e é denotado por rc(G). O Problema da Coloração Arco-Íris é NP-Completo. Poucas classes de grafos possuem um algoritmo eficiente conhecido para determinar rc(G). Este trabalho apresenta limitantes superiores justos para o número de conexão arco-íris em cografos, que são caracterizados por não possuírem Ρ4 induzido. | pt_BR |
dc.degree.local | Ponta Grossa | pt_BR |
dc.publisher.local | Ponta Grossa | pt_BR |
dc.contributor.advisor1 | Almeida, Sheila Morais de | |
dc.contributor.referee1 | Almeida, Sheila Morais de | |
dc.contributor.referee2 | Vignatti, Andre Luís | |
dc.contributor.referee3 | Queiroz, Saulo Jorge Beltrao de | |
dc.publisher.country | Brasil | pt_BR |
dc.publisher.department | Departamento Acadêmico de Informática | pt_BR |
dc.publisher.program | Ciência da Computação | pt_BR |
dc.publisher.initials | UTFPR | pt_BR |
dc.subject.cnpq | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO | pt_BR |
Aparece nas coleções: | PG - Ciência da Computação |
Arquivos associados a este item:
Arquivo | Descrição | Tamanho | Formato | |
---|---|---|---|---|
PG_COCIC_2018_2_08.pdf | 622,49 kB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.