Doctoral Thesis
DOI
Document
Author
Full name
Hugo Vinicius Vaz Braga
E-mail
Institute/School/College
Knowledge Area
Date of Defense
Published
São Paulo, 2018
Supervisor
Committee
Wakabayashi, Yoshiko (President)
Ferreira, Carlos Eduardo
Lima, Karla Roberta Pereira Sampaio
Meneses, Cláudio Nogueira de
Xavier, Eduardo Cândido
Title in Portuguese
Algoritmos exatos para problemas de spanner em grafos
Keywords in Portuguese
Algoritmo exato
Geração de coluna
Grafo
Spanner
Abstract in Portuguese
Title in English
Exact algorithms for spanner problems in graphs
Keywords in English
Column generation
Exact algorithm
Graph
Spanner
Abstract in English
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.

WARNING - Viewing this document is conditioned on your acceptance of the following terms of use:
This document is only for private use for research and teaching activities. Reproduction for commercial use is forbidden. This rights cover the whole data about this document as well as its contents. Any uses or copies of this document in whole or in part must include the author's name.
tese_HugoBraga.pdf (1.20 Mbytes)
Publishing Date
2019-04-18

WARNING: Learn what derived works are clicking here.
All rights of the thesis/dissertation are from the authors
CeTI-SC/STI