Coloração arco-íris para cografos
An edge coloring of a graph is a assignment of colors to the edges of the graph. The rainbow coloring is an assignment of these colors such that for every pair of vertices there is a path that does not repeat colors. These paths are called rainbow paths. The Rainbow Coloring Problem consists in dete...
| Autor principal: | D’Almeida, Diego Gonzales |
|---|---|
| Formato: | Trabalho de Conclusão de Curso (Graduação) |
| Idioma: | Português |
| Publicado em: |
Universidade Tecnológica Federal do Paraná
2020
|
| Assuntos: | |
| Acesso em linha: |
http://repositorio.utfpr.edu.br/jspui/handle/1/15977 |
| Tags: |
Adicionar Tag
Sem tags, seja o primeiro a adicionar uma tag!
|
| id |
riut-1-15977 |
|---|---|
| recordtype |
dspace |
| spelling |
riut-1-159772020-11-19T18:24:30Z Coloração arco-íris para cografos Rainbow coloring for cographs D’Almeida, Diego Gonzales Almeida, Sheila Morais de Almeida, Sheila Morais de Vignatti, Andre Luís Queiroz, Saulo Jorge Beltrao de Cores Grafos de ligação Arco-íris Colors Bond graphs Rainbow CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO An edge coloring of a graph is a assignment of colors to the edges of the graph. The rainbow coloring is an assignment of these colors such that for every pair of vertices there is a path that does not repeat colors. These paths are called rainbow paths. The Rainbow Coloring Problem consists in determining the least number of colors for a rainbow coloring of a given graph. This minimum number of colors is known as rainbow connection number and it is denotes by rc(G) for a graph G. The rainbow coloring Problem is NP-complete. There are efficient algorithms to solve it for few classes of graphs. This work presents a tight upper bound for the rainbow connection number of cographs, which are graphs without induced Ρ4. Uma coloração de arestas consiste na atribuição de cores às arestas do grafo. Uma forma de atribuição para essas cores é a coloração arco-íris. Essa coloração tem por característica a existência de um caminho que não repete cores entre cada par dos vértices do grafo - chamado de caminho arco-íris. O Problema da Coloração Arco-Íris consiste em encontrar o menor número de cores k para qual um grafo G possui uma coloração arco-íris. Esse k mínimo é chamado de número de conexão arco-íris e é denotado por rc(G). O Problema da Coloração Arco-Íris é NP-Completo. Poucas classes de grafos possuem um algoritmo eficiente conhecido para determinar rc(G). Este trabalho apresenta limitantes superiores justos para o número de conexão arco-íris em cografos, que são caracterizados por não possuírem Ρ4 induzido. 2020-11-19T18:24:30Z 2020-11-19T18:24:30Z 2018-11-20 bachelorThesis D’ALMEIDA, Diego Gonzales. Coloração arco-íris para cografos. 2018. 40 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/15977 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 |
Cores Grafos de ligação Arco-íris Colors Bond graphs Rainbow CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO |
| spellingShingle |
Cores Grafos de ligação Arco-íris Colors Bond graphs Rainbow CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO D’Almeida, Diego Gonzales Coloração arco-íris para cografos |
| description |
An edge coloring of a graph is a assignment of colors to the edges of the graph. The rainbow coloring is an assignment of these colors such that for every pair of vertices there is a path that does not repeat colors. These paths are called rainbow paths. The Rainbow Coloring Problem consists in determining the least number of colors for a rainbow coloring of a given graph. This minimum number of colors is known as rainbow connection number and it is denotes by rc(G) for a graph G. The rainbow coloring Problem is NP-complete. There are efficient algorithms to solve it for few classes of graphs. This work presents a tight upper bound for the rainbow connection number of cographs, which are graphs without induced Ρ4. |
| format |
Trabalho de Conclusão de Curso (Graduação) |
| author |
D’Almeida, Diego Gonzales |
| author_sort |
D’Almeida, Diego Gonzales |
| title |
Coloração arco-íris para cografos |
| title_short |
Coloração arco-íris para cografos |
| title_full |
Coloração arco-íris para cografos |
| title_fullStr |
Coloração arco-íris para cografos |
| title_full_unstemmed |
Coloração arco-íris para cografos |
| title_sort |
coloração arco-íris para cografos |
| publisher |
Universidade Tecnológica Federal do Paraná |
| publishDate |
2020 |
| citation |
D’ALMEIDA, Diego Gonzales. Coloração arco-íris para cografos. 2018. 40 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/15977 |
| _version_ |
1805317752882200576 |
| score |
10,814766 |