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/16009
Registro completo de metadados
Campo DCValorIdioma
dc.creatorBarchi, Tathiana Mikamura
dc.date.accessioned2020-11-19T18:25:52Z-
dc.date.available2020-11-19T18:25:52Z-
dc.date.issued2019-12-03
dc.identifier.citationBARCHI, Tathiana Mikamura. Coloração de vértices em grafos arco-circulares. 2019. Trabalho de Conclusão de Curso (Bacharelado em Ciência da Computação) - Universidade Tecnológica Federal do Paraná, Ponta Grossa, 2019.pt_BR
dc.identifier.urihttp://repositorio.utfpr.edu.br/jspui/handle/1/16009-
dc.description.abstractThe 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.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.subjectAlgorítmospt_BR
dc.subjectColorspt_BR
dc.subjectBond graphspt_BR
dc.subjectAlgorithmspt_BR
dc.titleColoração de vértices em grafos arco-circularespt_BR
dc.title.alternativeVertex coloring on circular-arc graphspt_BR
dc.typebachelorThesispt_BR
dc.description.resumoO 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.pt_BR
dc.degree.localPonta Grossapt_BR
dc.publisher.localPonta Grossapt_BR
dc.contributor.advisor1Maciel, Denise do Rocio
dc.contributor.advisor-co1Almeida, Sheila Morais de
dc.contributor.referee1Maciel, Denise do Rocio
dc.contributor.referee2Siqueira, Hugo Valadares
dc.contributor.referee3Zatesko, Leandro Miranda
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_2019_2_18.pdf720,86 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.