Busca avançada
Ano de início
Entree

Problemas sobre spanners em grafos

Processo: 19/14471-1
Linha de fomento:Bolsas no Brasil - Pós-Doutorado
Vigência (Início): 01 de fevereiro de 2020
Vigência (Término): 31 de janeiro de 2022
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
Pesquisador responsável:Flávio Keidi Miyazawa
Beneficiário:Renzo Gonzalo Gómez Diaz
Instituição-sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , 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):Algoritmos de aproximação   Grafos   Otimização combinatória   Computabilidade e complexidade

Resumo

Este projeto tem como foco o estudo de problemas sobre spanners em grafos. Dado um grafo conexo G e um número real positivo t > 1 (fator de dilatação), um t-spanner de G é um subgrafo gerador H de G tal que para todo par de vértices u e v, a distância entre u e v em H é no máximo t vezes a distância entre eles em G. Um problema central sobre este tópico, conhecido como o problema da árvore t-spanner, consiste em encontrar, dado um grafo conexo G, uma árvore que seja um t-spanner de G, ou concluir que não existe uma tal árvore. Quando o objetivo éencontrar um subgrafo com o menor número de arestas que seja um t-spanner, temos o problema do t-spanner mínimo. Para t fixo, o único caso em que a complexidade não foi estabelecida é o caso em que t = 3. Neste projeto pretendemos investigar problemas sobre spanners em grafos, com ênfase nos seus aspectos algorítmicos e de complexidade computacional. Temos interesse em ampliar as classes de grafos para as quais estes problemas podem ser resolvidos em tempo polinomial, e também focaremos no caso especial em que t = 3. Pretendemos investigar estes problemas com abordagens novas (algoritmos de aproximação ou métodos exatos) e, assim, contribuir com resultados algorítmicos e de complexidade computacional que avancem o estado-da-arte destes problemas. (AU)