DOI
Documento
Autor
Nome completo
Hugo Vinicius Vaz Braga
E-mail
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2018
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
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