Doctoral Thesis
Document
Doctoral Thesis
Author
Full name
Santiago Valdes Ravelo
E-mail
Institute/School/College
Instituto de Matemática e Estatística
Knowledge Area
Date of Defense
2016-02-18
Published
São Paulo, 2016
Supervisor
Committee
Ferreira, Carlos Eduardo (President)
Gruber, Aritanan Borges Garcia
Lee, Orlando
Meira, Luis Augusto Angelotti
Schouery, Rafael Crivellari Saliba
Title in Portuguese
Problema da árvore geradora de comunicação ótima: variantes, complexidade e aproximação
Keywords in Portuguese
Algoritmos de aproximação, Árvore geradora de comunicação ótima, Otimização combinatória
Abstract in Portuguese
O problema da árvore geradora de comunicação ótima recebe um grafo com comprimentos não negativos nas arestas e um requerimento não negativo entre cada par de vértices; sendo o objetivo encontrar uma árvore geradora do grafo que minimize o custo de comunicação, que é a soma sobre cada par de vértice da distância entre eles na árvore vezes o requerimento entre eles. Este problema é NP-difícil, assim como vários casos particulares dele. Neste trabalho estudamos algumas variantes deste problema, introduzimos novos casos particulares que são também NP-difíceis e propomos esquemas de aproximação polinomial para alguns deles.
Title in English
Optimum communication spanning tree problem: variants, complexity and approximation
Keywords in English
Approximation algorithms, Combinatorial optimization, Optimum communication spanning tree
Abstract in English
The optimum communication spanning tree problem receives a graph with non-negative lengths over the edges and non-negative requirements for each pair of nodes; being the objective to find a spanning tree of the graph that minimizes the communication cost, which is given by the sum, over each pair of nodes, of the distance, in the tree, between the nodes multiplied by the requirement between them. This problem and several of its particular cases are NP-hard. In this work we study some of the variants, also we introduce new NP-hard particular cases of the problem and propose polynomial approximation schemes for some of them.
WARNING - Viewing this document is conditioned on acceptance of the terms of use. This document is for private use in research and teaching activities only.
Publishing Date
2016-04-25
Derived works
WARNING: Learn what derived works are in the digital library guidance pages.