Aumento de conexidade de grafos e redes robustas

• Processo: 21/12599-0
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de março de 2022
• Data de Término da vigência: 30 de novembro de 2023
• Á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: Gabriel Morete de Azevedo
• 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
• Bolsa(s) vinculada(s): 22/15632-1 - Aumento de conexidade de grafos e redes robustas, BE.EP.MS
• Assunto(s): Algoritmos de aproximação Otimização combinatória Teoria dos grafos
• Palavra(s)-Chave do Pesquisador: Algoritmos de Aproximação | aumento de conexidade de grafos | Otimização Combinatória | teoria dos grafos | Algoritmos de aproximação

Resumo

Este é um projeto de pesquisa para o mestrado de Gabriel Morete de Azevedo, a ser desenvolvido sob a orientação de Y.Wakabayashi, no IME-USP. Este se insere na área de otimização combinatória, e tem como foco problemas de aumento de conexidade em grafos, com ênfase em seus aspectos algorítmicos. Em linhas gerais, os problemas focados têm como objetivo aumentar a conexidade de um grafo de entrada, de forma econômica, acrescentando-se arestas de um certo conjunto dado (aos quais estão associdados custos não negativos). Serão investigadas algumas variantes desses problemas, considerando-se vértice-conexidade ou aresta-conexidade. Quando o grafo modela, por exemplo, uma rede de comunicação, de transporte ou de energia, esses parâmetros indicam a robustez (grau de tolerância a falha) da rede, sendo de grande interesse tanto prático como teórico. No caso geral, tais problemas são todos computacionalmente difíceis. Ao estudar as diversas variantes, o candidato será exposto a diversas técnicas algorítmicas que são importantes para sua formação na área de otimização combinatória, em especial, no desenvolvimento de algoritmos de aproximação.