Use este identificador para citar ou linkar para este item: http://repositorio.roca.utfpr.edu.br/jspui/handle/1/9737
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
Referência: 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.roca.utfpr.edu.br/jspui/handle/1/9737
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 PDFVisualizar/Abrir


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