کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10225744 | 1701209 | 2018 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Approximating Steiner trees and forests with minimum number of Steiner points
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Let R be a finite set of terminals in a convex metric space (M,d). We give approximation algorithms for problems of finding a minimum size set SâM of additional points such that the unit-disc graph G[RâªS] of RâªS satisfies some connectivity properties. Let Î be the maximum number of independent points in a unit ball. For the Steiner Treewith Minimum Number of Steiner Points problem we obtain approximation ratio 1+lnâ¡(Îâ1)+ϵ, which in R2 reduces to 1+lnâ¡4+ϵ<2.3863+ϵ; this improves the ratios â(Î+1)/2â+1+ϵ of [19] and 2.5+ϵ of [7], respectively. For the Steiner Forestwith Minimum Number of Steiner Points problem we give a simple Î-approximation algorithm, improving the ratio 2(Îâ1) of [21]. We also simplify the Î-approximation of [4], when G[RâªS] should be 2-connected.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 98, December 2018, Pages 53-64
Journal: Journal of Computer and System Sciences - Volume 98, December 2018, Pages 53-64
نویسندگان
Nachshon Cohen, Zeev Nutov,