Registro fonte: Coloração biclique em cografos

Coloração biclique em cografos

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...

ver descrição completa

Autor principal:	Cararo, Cintia Izabel
Formato:	Trabalho de Conclusão de Curso (Graduação)
Idioma:	Português
Publicado em:	Universidade Tecnológica Federal do Paraná 2020
Assuntos:	Grafos de ligação Algorítmos computacionais Árvores (Teoria dos grafos) Bond graphs Computer algorithms Trees (Graph theory) CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Acesso em linha:	http://repositorio.utfpr.edu.br/jspui/handle/1/15968
Tags:	Adicionar Tag Sem tags, seja o primeiro a adicionar uma tag!

id	riut-1-15968
recordtype	dspace
spelling	riut-1-159682020-11-19T18:24:11Z Coloração biclique em cografos Biclique coloring cographs Cararo, Cintia Izabel Almeida, Sheila Morais de Almeida, Sheila Morais de Kossoski, Clayton Matos, Simone Nasser Grafos de ligação Algorítmos computacionais Árvores (Teoria dos grafos) Bond graphs Computer algorithms Trees (Graph theory) CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO 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. 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. 2020-11-19T18:24:10Z 2020-11-19T18:24:10Z 2018-06-12 bachelorThesis 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. http://repositorio.utfpr.edu.br/jspui/handle/1/15968 por openAccess application/pdf Universidade Tecnológica Federal do Paraná Ponta Grossa Brasil Departamento Acadêmico de Informática Ciência da Computação UTFPR
institution	Universidade Tecnológica Federal do Paraná
collection	RIUT
language	Português
topic	Grafos de ligação Algorítmos computacionais Árvores (Teoria dos grafos) Bond graphs Computer algorithms Trees (Graph theory) CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
spellingShingle	Grafos de ligação Algorítmos computacionais Árvores (Teoria dos grafos) Bond graphs Computer algorithms Trees (Graph theory) CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO Cararo, Cintia Izabel Coloração biclique em cografos
description	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.
format	Trabalho de Conclusão de Curso (Graduação)
author	Cararo, Cintia Izabel
author_sort	Cararo, Cintia Izabel
title	Coloração biclique em cografos
title_short	Coloração biclique em cografos
title_full	Coloração biclique em cografos
title_fullStr	Coloração biclique em cografos
title_full_unstemmed	Coloração biclique em cografos
title_sort	coloração biclique em cografos
publisher	Universidade Tecnológica Federal do Paraná
publishDate	2020
citation	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.
url	http://repositorio.utfpr.edu.br/jspui/handle/1/15968
_version_	1805314898758991872
score	10,814766

Coloração biclique em cografos

Registros relacionados