| Processo: | 19/14471-1 |
| Modalidade de apoio: | Bolsas no Brasil - Pós-Doutorado |
| Data de Início da vigência: | 01 de fevereiro de 2020 |
| Data de Término da vigência: | 28 de fevereiro de 2023 |
| Área de 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 |
| Palavra(s)-Chave do Pesquisador: | Algoritmos de Aproximação | árvore geradora | Complexidade Computacional | grafos | spanners | Otimzação Combinatória |
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) | |
| Matéria(s) publicada(s) na Agência FAPESP sobre a bolsa: | |
| Mais itensMenos itens | |
| TITULO | |
| Matéria(s) publicada(s) em Outras Mídias ( ): | |
| Mais itensMenos itens | |
| VEICULO: TITULO (DATA) | |
| VEICULO: TITULO (DATA) | |