• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Tesis Doctoral
DOI
10.11606/T.45.2016.tde-12042016-145246
Documento
Autor
Nombre completo
Santiago Valdes Ravelo
Dirección Electrónica
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Paulo, 2016
Director
Tribunal
Ferreira, Carlos Eduardo (Presidente)
Gruber, Aritanan Borges Garcia
Lee, Orlando
Meira, Luis Augusto Angelotti
Schouery, Rafael Crivellari Saliba
Título en portugués
Problema da árvore geradora de comunicação ótima: variantes, complexidade e aproximação
Palabras clave en portugués
Algoritmos de aproximação
Árvore geradora de comunicação ótima
Otimização combinatória
Resumen en portugués
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.
Título en inglés
Optimum communication spanning tree problem: variants, complexity and approximation
Palabras clave en inglés
Approximation algorithms
Combinatorial optimization
Optimum communication spanning tree
Resumen en inglés
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.
 
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_santiago.pdf (1.18 Mbytes)
Fecha de Publicación
2016-04-25
 
ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.
Todos los derechos de la tesis/disertación pertenecen a los autores
CeTI-SC/STI
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2021. Todos los derechos reservados.