Thèse de Doctorat
DOI
https://doi.org/10.11606/T.45.2019.tde-01042019-093402
Document
Auteur
Nom complet
Hugo Vinicius Vaz Braga
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Paulo, 2018
Directeur
Jury
Wakabayashi, Yoshiko (Président)
Ferreira, Carlos Eduardo
Lima, Karla Roberta Pereira Sampaio
Meneses, Cláudio Nogueira de
Xavier, Eduardo Cândido
Titre en portugais
Algoritmos exatos para problemas de spanner em grafos
Mots-clés en portugais
Algoritmo exato
Geração de coluna
Grafo
Spanner
Resumé en portugais
Titre en anglais
Exact algorithms for spanner problems in graphs
Mots-clés en anglais
Column generation
Exact algorithm
Graph
Spanner
Resumé en anglais
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.

AVERTISSEMENT - Regarde ce document est soumise à votre acceptation des conditions d'utilisation suivantes:
Ce document est uniquement à des fins privées pour la recherche et l'enseignement. Reproduction à des fins commerciales est interdite. Cette droits couvrent l'ensemble des données sur ce document ainsi que son contenu. Toute utilisation ou de copie de ce document, en totalité ou en partie, doit inclure le nom de l'auteur.
tese_HugoBraga.pdf (1.20 Mbytes)
Date de Publication
2019-04-18

AVERTISSEMENT: Apprenez ce que sont des œvres dérivées cliquant ici.
Tous droits de la thèse/dissertation appartiennent aux auteurs
CeTI-SC/STI
Bibliothèque Numérique de Thèses et Mémoires de l'USP. Copyright © 2001-2024. Tous droits réservés.