Busca avançada
Ano de início
Entree

Aumento de conexidade de grafos e redes robustas

Processo: 22/15632-1
Modalidade de apoio:Bolsas no Exterior - Estágio de Pesquisa - Mestrado
Vigência (Início): 01 de fevereiro de 2023
Vigência (Término): 31 de maio de 2023
Á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: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
Local de pesquisa: 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)

Matéria(s) publicada(s) na Agência FAPESP sobre a bolsa:
Matéria(s) publicada(s) em Outras Mídias (0 total):
Mais itensMenos itens
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)