Busca avançada
Ano de início
Entree

Problemas de Rotulação em Grafos

Processo: 17/26114-3
Linha de fomento:Bolsas no Brasil - Pós-Doutorado
Vigência (Início): 01 de setembro de 2018
Vigência (Término): 28 de janeiro de 2019
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
Pesquisador responsável:Yoshiko Wakabayashi
Beneficiário:Atilio Gomes Luiz
Instituição-sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
Vinculado ao auxílio:15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural, AP.TEM
Assunto(s):Teoria dos grafos

Resumo

Este é o projeto de pesquisa de pós-doutorado de Atílio Gomes Luiz, a ser desenvolvido sob a supervisão da Profa. Dra. Yoshiko Wakabayashi, no Instituto de Matemática e Estatística, USP. Este projeto se insere na área de Teoria dos Grafos e tem como foco problemas clássicos sobre rotulação de grafos. Nesses problemas, o objetivo é atribuir inteiros não-negativos aos elementos (vértices ou arestas) de um grafo, sujeito a determinadas condições. Existem diversos problemas de rotulação em grafos, que se diferenciam pelos objetos que são rotulados, e as propriedades que as rotulações devem satisfazer. Problemas bem conhecidos como coloração de vértices ou de arestas também são problemas de rotulação. Muitos problemas de rotulação foram motivados por aplicações práticas, tais como atribuição de frequências de rádio a transmissores, atribuição de códigos corretores de erros a chips de computadores e projeto decircuitos ótimos. Além disso, algumas rotulações também são utilizadas como ferramentas para estudar outros problemas, como por exemplo, decomposição de grafos. Neste projeto propõe-se a investigação de três problemas de rotulação em grafos, que são interessantes e relevantes tanto do ponto de vista prático quanto teórico. São eles: a L(2,1)-rotulação, a rotulação graciosa e a rotulação aresta-mágica de grafos.