Algoritmos exatos para problemas de spanner em grafos (2018)
- Autores:
- Autor USP: BRAGA, HUGO VINICIUS VAZ - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Assunto: CIENCIA DA COMPUTACAO
- Palavras-chave do autor: Algoritmo exato; Column generation; Exact algorithm; Geração de coluna; Grafo; Graph; Spanner; Spanner
- Agências de fomento:
- Idioma: Português
- Resumo: Seja (G,w,t) uma tripla formada por um grafo conexo G = (V,E), uma função peso não-negativa w definida em E e um número real t >= 1, chamado de fator de dilatação. Um t-spanner de G é um subgrafo gerador H de G tal que para cada par 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. Quando H é uma árvore, dizemos que H é uma árvore t-spanner. Nesta tese focamos o problema da árvore t- spanner de peso mínimo (cuja sigla em inglês é MWTSP), definido a seguir. Dada uma tripla (G,w,t), encontrar uma árvore t-spanner em G de peso mínimo. É sabido que MWTSP é NP-difícil para cada t > 1 fixo. Propomos duas formulações lineares inteiras para MWTSP, baseadas em arborescência, de tamanho polinomial no tamanho de G. A formulação que possui variáveis representando distâncias entres os pares de vértices apresentou resultados melhores na prática. Também abordamos o problema de t-spanner de peso mínimo (cuja sigla em inglês é MWSP), cuja entrada é a mesma do MWTSP e cujo objetivo é encontrar um t-spanner de peso mínimo. Mesmo para grafos com peso unitário, MWSP é NP-difícil para cada t >= 2 fixo. Tratamos este problema de duas formas. Propomos uma formulação linear inteira para o MWSP que possui um número exponencial de restrições, mas cujo problema da separação para o programa linear relaxado correspondente é polinomial no tamanho de G. Apresentamos também uma implementação de um algoritmo de branch-and-price para o MWSP baseado numaformulação linear inteira proposta por Sigurd e Zachariasen (2004). Exibimos resultados de experimentos realizados com as duas formulações para o MWTSP e também com o algoritmo de branch-and-price para o MWSP
- Imprenta:
- Data da defesa: 14.12.2018
-
ABNT
BRAGA, Hugo Vinicius Vaz. Algoritmos exatos para problemas de spanner em grafos. 2018. Tese (Doutorado) – Universidade de São Paulo, São Paulo, 2018. Disponível em: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-01042019-093402/. Acesso em: 10 nov. 2024. -
APA
Braga, H. V. V. (2018). Algoritmos exatos para problemas de spanner em grafos (Tese (Doutorado). Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45134/tde-01042019-093402/ -
NLM
Braga HVV. Algoritmos exatos para problemas de spanner em grafos [Internet]. 2018 ;[citado 2024 nov. 10 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-01042019-093402/ -
Vancouver
Braga HVV. Algoritmos exatos para problemas de spanner em grafos [Internet]. 2018 ;[citado 2024 nov. 10 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-01042019-093402/
Como citar
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
