Aumento de conexidade de grafos e redes robustas

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 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.