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. / 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.
| Identifer | oai:union.ndltd.org:usp.br/oai:teses.usp.br:tde-12042016-145246 |
| Date | 18 February 2016 |
| Creators | Ravelo, Santiago Valdes |
| Contributors | Ferreira, Carlos Eduardo |
| Publisher | Biblioteca Digitais de Teses e Dissertações da USP |
| Source Sets | Universidade de São Paulo |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | Tese de Doutorado |
| Format | application/pdf |
| Rights | Liberar o conteúdo para acesso público. |
Page generated in 0.0023 seconds