Spanners em Grafos

• Processo: 13/22875-9
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Data de Início da vigência: 01 de março de 2014
• Data de Término da vigência: 28 de fevereiro de 2018
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Yoshiko Wakabayashi
• Beneficiário: Hugo Vinicius Vaz Braga
• Instituição Sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
• Assunto(s): Programação linear Grafos Complexidade computacional
• Palavra(s)-Chave do Pesquisador: agoritmos | Complexidade Computacional | grafos | inaproximabilidade | programação linear | spanners | Grafos e Otimização Combinatória

Resumo

Este projeto tem como foco 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 quaisquer pares de vértices u, v, a distância entre u e v em H é no máximo t vezes a distância entre u e v em G. Um problema central sobre este tópico, conhecido como o problema do t-spanner mínimo, consiste em encontrar num dado grafo conexo G, um t-spanner com o menor número possível de arestas. Quando o objetivo é encontrar (se existente) um t-spanner que seja uma árvore, temos o chamado problema de árvore t-spanner. Ambos os problemas são computacionalmente difíceis quando t é pelo menos 4. Neste projeto, pretendemos investigar problemas sobre spanners em grafos, com ênfase nos seus aspectos algorítmicos e de complexidade computacional, priorizando mas não nos restringindo ao problema de árvore t-spanner. Spanners têm aplicações em redes de comunicação, computação distribuída, robótica e outras áreas.

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

BRAGA, Hugo Vinicius Vaz. Algoritmos exatos para problemas de spanner em grafos. 2018. Tese de Doutorado - Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI) São Paulo.