1. Repositório Institucional da Universidade Tecnológica Federal do Paraná (RIUT)
  2. GRAD - Cursos de Graduação
  3. TCC - Trabalhos de Conclusão de Curso de Graduação
  4. Ponta Grossa
  5. PG - Ciência da Computação
Use este identificador para citar ou linkar para este item: http://repositorio.utfpr.edu.br/jspui/handle/1/15977
Registro completo de metadados
Campo DCValorIdioma
dc.creatorD’Almeida, Diego Gonzales
dc.date.accessioned2020-11-19T18:24:30Z-
dc.date.available2020-11-19T18:24:30Z-
dc.date.issued2018-11-20
dc.identifier.citationD’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.urihttp://repositorio.utfpr.edu.br/jspui/handle/1/15977-
dc.description.abstractAn 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.languageporpt_BR
dc.publisherUniversidade Tecnológica Federal do Paranápt_BR
dc.rightsopenAccesspt_BR
dc.subjectCorespt_BR
dc.subjectGrafos de ligaçãopt_BR
dc.subjectArco-írispt_BR
dc.subjectColorspt_BR
dc.subjectBond graphspt_BR
dc.subjectRainbowpt_BR
dc.titleColoração arco-íris para cografospt_BR
dc.title.alternativeRainbow coloring for cographspt_BR
dc.typebachelorThesispt_BR
dc.description.resumoUma 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.localPonta Grossapt_BR
dc.publisher.localPonta Grossapt_BR
dc.contributor.advisor1Almeida, Sheila Morais de
dc.contributor.referee1Almeida, Sheila Morais de
dc.contributor.referee2Vignatti, Andre Luís
dc.contributor.referee3Queiroz, Saulo Jorge Beltrao de
dc.publisher.countryBrasilpt_BR
dc.publisher.departmentDepartamento Acadêmico de Informáticapt_BR
dc.publisher.programCiência da Computaçãopt_BR
dc.publisher.initialsUTFPRpt_BR
dc.subject.cnpqCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAOpt_BR
Aparece nas coleções:PG - Ciência da Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
PG_COCIC_2018_2_08.pdf622,49 kBAdobe PDFThumbnail
Visualizar/Abrir
Mostrar registro simples do item Recomendar este item Visualizar estatísticas


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.