کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
431266 | 688489 | 2015 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Bottleneck Steiner tree with bounded number of Steiner vertices
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Given a complete graph G=(V,E)G=(V,E), where each vertex is labeled either terminal or Steiner, a distance function (i.e., a metric) d:E→R+d:E→R+, and a positive integer k, we study the problem of finding a Steiner tree T spanning all terminals and at most k Steiner vertices, such that the length of the longest edge is minimized. We first show that this problem is NP-hard and cannot be approximated within a factor of 2−ε2−ε, for any ε>0ε>0, unless P=NPP=NP. Then, we present a polynomial-time 2-approximation algorithm for this problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 30, January 2015, Pages 96–100
Journal: Journal of Discrete Algorithms - Volume 30, January 2015, Pages 96–100
نویسندگان
A. Karim Abu-Affash, Paz Carmi, Matthew J. Katz,