Busca avançada
Ano de início
Entree

Spanners em Grafos

Processo: 13/22875-9
Modalidade de apoio:Bolsas no Brasil - Doutorado
Vigência (Início): 01 de março de 2014
Vigência (Término): 28 de fevereiro de 2018
Á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: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.

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)

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.

Por favor, reporte erros na lista de publicações científicas utilizando este formulário.