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. Curitiba
  5. CT - Sistemas de Informação
Use este identificador para citar ou linkar para este item: http://repositorio.utfpr.edu.br/jspui/handle/1/9220
Registro completo de metadados
Campo DCValorIdioma
dc.creatorRogiski, Rosana
dc.date.accessioned2020-11-12T12:01:57Z-
dc.date.available2020-11-12T12:01:57Z-
dc.date.issued2016-06-27
dc.identifier.citationROGISKI, Rosana. Desempenho do algoritmo guloso na coloração de vértices em grafos de sistemas complexos. 2016. 99 f. Trabalho de Conclusão de Curso (Bacharelado em Sistemas da Informação) - Universidade Tecnológica Federal do Paraná, Curitiba, 2016.pt_BR
dc.identifier.urihttp://repositorio.utfpr.edu.br/jspui/handle/1/9220-
dc.description.abstractIn this work we aim to study the performance of greedy technique in the vertex coloring problem for graphs from Complex Systems. For doing that, twenty-five Complex Systems were selected, and from them we obtained the underlying graph on which the tests were performed. Two greedy heuristics for choosing the next vertex to be colored were analyzed: the first one uses the greatest degree heuristic for selecting the next vertex to be colored, and the second one applies the greatest saturation heuristic combined with the greatest degree heuristic. The results were compared with the optimal solution and some of the boundaries to the vertex coloring problem.pt_BR
dc.languageporpt_BR
dc.publisherUniversidade Tecnológica Federal do Paranápt_BR
dc.rightsopenAccesspt_BR
dc.subjectAlgorítmospt_BR
dc.subjectTeoria dos grafospt_BR
dc.subjectProgramação heurísticapt_BR
dc.subjectAlgorítmos computacionaispt_BR
dc.subjectAlgorithmspt_BR
dc.subjectComputer algorithmspt_BR
dc.subjectGraph theorypt_BR
dc.subjectHeuristic programmingpt_BR
dc.titleDesempenho do algoritmo guloso na coloração de vértices em grafos de sistemas complexospt_BR
dc.title.alternativePerformance of greedy algorithm for vertex coloring in graphs from complex systemspt_BR
dc.typebachelorThesispt_BR
dc.description.resumoNeste trabalho buscamos estudar o desempenho da técnica gulosa no problema de coloração de vértices em grafos oriundos de Sistemas Complexos. Para tanto, foram selecionados grafos de vinte e cinco Sistemas Complexos e obtidos seus grafos subjacentes sobre os quais foram executados os testes. Foram analisadas duas heurísticas gulosas para a escolha do próximo vértice a colorir: a primeira utilizando a heurística do maior grau para seleção do próximo vértice a colorir e a segunda utilizando a heurística da maior saturação combinada com maior grau. Os resultados foram comparados com a solução ótima e alguns limitantes do problema de coloração de vértices.pt_BR
dc.degree.localCuritibapt_BR
dc.publisher.localCuritibapt_BR
dc.contributor.advisor1Murilo, Vicente Gonçalves da Silva
dc.contributor.referee1Minetto, Rodrigo
dc.contributor.referee2Silva, Ricardo Dutra da
dc.contributor.referee3Silva, Murilo Vicente Gonçalves da
dc.publisher.countryBrasilpt_BR
dc.publisher.programBacharelado em Sistemas de Informaçãopt_BR
dc.publisher.initialsUTFPRpt_BR
dc.subject.cnpqCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO::ANALISE DE ALGORITMOS E COMPLEXIDADE DE COMPUTACAOpt_BR
Aparece nas coleções:CT - Sistemas de Informação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
CT_COSIS_2016_3.pdf1,49 MBAdobe 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.