Tesis Doctoral
DOI
Documento
Autor
Nombre completo
Hugo Vinicius Vaz Braga
Dirección Electrónica
Área de Conocimiento
Fecha de Defensa
Publicación
São Paulo, 2018
Director
Tribunal
Wakabayashi, Yoshiko (Presidente)
Ferreira, Carlos Eduardo
Lima, Karla Roberta Pereira Sampaio
Meneses, Cláudio Nogueira de
Xavier, Eduardo Cândido
Título en portugués
Algoritmos exatos para problemas de spanner em grafos
Palabras clave en portugués
Algoritmo exato
Geração de coluna
Grafo
Spanner
Resumen en portugués
Título en inglés
Exact algorithms for spanner problems in graphs
Palabras clave en inglés
Column generation
Exact algorithm
Graph
Spanner
Resumen en 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.

ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
tese_HugoBraga.pdf (1.20 Mbytes)
Fecha de Publicación
2019-04-18