Algoritmos exatos para problemas de spanner em grafos (2018)
- Authors:
- Autor USP: BRAGA, HUGO VINICIUS VAZ - IME
- Unidade: IME
- Sigla do Departamento: MAC
- DOI: 10.11606/T.45.2019.tde-01042019-093402
- Assunto: CIENCIA DA COMPUTACAO
- Keywords: Algoritmo exato; Column generation; Exact algorithm; Geração de coluna; Grafo; Graph; Spanner; Spanner
- Agências de fomento:
- Language: Português
- Abstract: 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
- Status:
- Artigo possui versão em acesso aberto em repositório (Green Open Access)
- Versão do Documento:
- Versão submetida (Pré-print)
- Acessar versão aberta:
-
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: https://teses.usp.br/teses/disponiveis/45/45134/tde-01042019-093402/. Acesso em: 23 mar. 2026. -
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 https://teses.usp.br/teses/disponiveis/45/45134/tde-01042019-093402/ -
NLM
Braga HVV. Algoritmos exatos para problemas de spanner em grafos [Internet]. 2018 ;[citado 2026 mar. 23 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-01042019-093402/ -
Vancouver
Braga HVV. Algoritmos exatos para problemas de spanner em grafos [Internet]. 2018 ;[citado 2026 mar. 23 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-01042019-093402/
Informações sobre a disponibilidade de versões do artigo em acesso aberto coletadas automaticamente via oaDOI API (Unpaywall).
Por se tratar de integração com serviço externo, podem existir diferentes versões do trabalho (como preprints ou postprints), que podem diferir da versão publicada.
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
