کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949566 | 1440195 | 2017 | 18 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A PTAS for the metric case of the minimum sum-requirement communication spanning tree problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 228, 10 September 2017, Pages 158-175
Journal: Discrete Applied Mathematics - Volume 228, 10 September 2017, Pages 158-175
نویسندگان
S.V. Ravelo, C.E. Ferreira,