Use este identificador para citar ou linkar para este item:
http://repositorio.utfpr.edu.br/jspui/handle/1/15968| Título: | Coloração biclique em cografos |
| Título(s) alternativo(s): | Biclique coloring cographs |
| Autor(es): | Cararo, Cintia Izabel |
| Orientador(es): | Almeida, Sheila Morais de |
| Palavras-chave: | Grafos de ligação Algorítmos computacionais Árvores (Teoria dos grafos) Bond graphs Computer algorithms Trees (Graph theory) |
| Data do documento: | 12-Jun-2018 |
| Editor: | Universidade Tecnológica Federal do Paraná |
| Câmpus: | Ponta Grossa |
| Citação: | CARARO, 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. |
| Resumo: | Uma κ-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. |
| Abstract: | A κ-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. |
| URI: | http://repositorio.utfpr.edu.br/jspui/handle/1/15968 |
| Aparece nas coleções: | PG - Ciência da Computação |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| PG_COCIC_2018_1_06.pdf | 1,17 MB | 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.