Problemas de Rotulação em Grafos

• Processo: 17/26114-3
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Data de Início da vigência: 01 de setembro de 2018
• Data de Término da vigência: 28 de janeiro de 2019
• Área de 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
• Palavra(s)-Chave do Pesquisador: L(2 | rotulação aresta-mágica | rotulação de grafos | rotulação graciosa | 1)-rotulação de grafos | 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.