Article ID Journal Published Year Pages File Type
4949566 Discrete Applied Mathematics 2017 18 Pages PDF
Abstract
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 ω(e) associated to the edges satisfying the triangular inequality and non-negative routing weights r(u) associated to nodes u∈V, the objective is to find a spanning tree T of G, that minimizes: 12∑u∈V∑v∈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⊆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.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,