Aumento de conexidade de grafos e redes robustas

• Processo: 22/15632-1
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Mestrado
• Data de Início da vigência: 01 de fevereiro de 2023
• Data de Término da vigência: 31 de maio 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
• Supervisor: Joseph Cheriyan
• Instituição Sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
• Instituição Anfitriã: University of Waterloo, Canadá
• Vinculado à bolsa: 21/12599-0 - Aumento de conexidade de grafos e redes robustas, BP.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 é o projeto de pesquisa BEPE-Mestrado de Gabriel Morete de Azevedo, mestrando no Instituto de Matemática e Estatística da Universidade de São Paulo, a se realizado no Combinatorics & Optimization Department da University of Waterloo, sob a supervisão do Professor Joseph Cheriyan. 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 associados 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. (AU)