| Texto completo | |
| Autor(es): |
Ravelo, S. V.
;
Ferreira, C. E.
Número total de Autores: 2
|
| Tipo de documento: | Artigo Científico |
| Fonte: | DISCRETE APPLIED MATHEMATICS; v. 228, p. 18-pg., 2017-09-10. |
| Resumo | |
This work considers the metric case of the minimum sum-requirement communication spanning tree problem (SROCT), which is an NP-hard particular case of the minimum communication spanning tree problem (OCT). Given an undirected graph G = (V, E) with non-negative lengths omega(e) associated to the edges satisfying the triangular inequality and non-negative routing weights r(u) associated to nodes u E V, the objective is to find a spanning tree T of G, that minimizes: 1/2 Sigma u is an element of V Sigma u is an element of V (r(u) + r(v)) d(T, u, v), where d(H, x, y) is the minimum distance between nodes x and y in a graph H subset of G. We present a polynomial approximation scheme for the metric case of the SROCT improving the until now best existing approximation algorithm for this problem. (C) 2016 Elsevier B.V. All rights reserved. (AU) | |
| Processo FAPESP: | 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação |
| Beneficiário: | Carlos Eduardo Ferreira |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |