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/15968
Registro completo de metadados
Campo DCValorIdioma
dc.creatorCararo, Cintia Izabel
dc.date.accessioned2020-11-19T18:24:10Z-
dc.date.available2020-11-19T18:24:10Z-
dc.date.issued2018-06-12
dc.identifier.citationCARARO, Cintia Izabel. Coloração biclique em cografos. 2018. 59 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/15968-
dc.description.abstractA κ-biclique coloring is an assignment of κ colors to the vertices of a graph so that its maximal bipartite induced subgraphs are not monochromatic. To decide if a graph has a κ-biclique coloring for a given κ is a _Ρ2 -complete problem. This paper presents a linear solution to the Biclique Coloring Problem in a subclass of cographs. Furthermore, new algorithms to enumerate the maximal independent sets and bicliques and to count bicliques in cographs are presented.pt_BR
dc.languageporpt_BR
dc.publisherUniversidade Tecnológica Federal do Paranápt_BR
dc.rightsopenAccesspt_BR
dc.subjectGrafos de ligaçãopt_BR
dc.subjectAlgorítmos computacionaispt_BR
dc.subjectÁrvores (Teoria dos grafos)pt_BR
dc.subjectBond graphspt_BR
dc.subjectComputer algorithmspt_BR
dc.subjectTrees (Graph theory)pt_BR
dc.titleColoração biclique em cografospt_BR
dc.title.alternativeBiclique coloring cographspt_BR
dc.typebachelorThesispt_BR
dc.description.resumoUma κ-coloração biclique é a atribuição de κ cores aos vértices de um grafo de modo que nenhum subgrafo induzido bipartido completo maximal seja monocromático. Decidir se um grafo tem uma κ-coloração biclique para um dado κ é um problema _Ρ2 -completo. Este trabalho apresenta solução em tempo linear para o Problema da Coloração Biclique em uma subclasse dos cografos. Além disso, são apresentados novos algoritmos para enumeração de conjuntos independentes maximais, enumeração de bicliques e contagem de bicliques em cografos.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.referee2Kossoski, Clayton
dc.contributor.referee3Matos, Simone Nasser
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_1_06.pdf1,17 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.