• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Tese de Doutorado
DOI
https://doi.org/10.11606/T.45.2019.tde-01042019-093402
Documento
Autor
Nome completo
Hugo Vinicius Vaz Braga
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2018
Orientador
Banca examinadora
Wakabayashi, Yoshiko (Presidente)
Ferreira, Carlos Eduardo
Lima, Karla Roberta Pereira Sampaio
Meneses, Cláudio Nogueira de
Xavier, Eduardo Cândido
Título em português
Algoritmos exatos para problemas de spanner em grafos
Palavras-chave em português
Algoritmo exato
Geração de coluna
Grafo
Spanner
Resumo em português
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 numa formulaçã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.
Título em inglês
Exact algorithms for spanner problems in graphs
Palavras-chave em inglês
Column generation
Exact algorithm
Graph
Spanner
Resumo em inglês
Let (G, w, t) be a triplet consisting of a connected graph G = (V, E) with a nonnegative weight function w defined on E, and a real number t >= 1. A t-spanner of G is a spanning subgraph H of G such that for each pair of vertices u,v, the distance between u and v in H is at most t times the distance between u and v in G. If H is a tree then we call it a tree t-spanner of G. We address the Minimum Weight Tree Spanner Problem (MWTSP), defined as follows. Given a triplet (G, w, t), find a minimum weight tree t-spanner in G. It is known that MWTSP is NP-hard for every fixed t > 1. We propose two ILP formulations for MWTSP, based on arborescences, of polynomial size in the size of G. The formulation that has variables representing distances between pairs of vertices has shown to be better in practice. We also address the Minimum Weight t-Spanner Problem (MWSP) that has the same input as MWTSP and seeks for a minimum weight t-spanner in G. Even for unweighted graphs, it is known that MWSP is NP-hard for every fixed t >= 2. We approach this problem in two ways. We propose an ILP formulation for MWSP that has an an exponential number of restrictions but we show that the separation problem for the corresponding relaxed linear program can be solved in polynomial time in the size of G. We also present a branch-and-price algorithm for MWSP based on an ILP formulation proposed by Sigurd and Zachariasen (2004). We show results on the computational experiments with both formulations for MWTSP and also with the branch-and-price algorithm that we implemented for MWSP.
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
tese_HugoBraga.pdf (1.20 Mbytes)
Data de Publicação
2019-04-18
 
AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
CeTI-SC/STI
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2024. Todos os direitos reservados.