Problemas sobre spanners em grafos

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)