کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414262 | 680868 | 2015 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On full Steiner trees in unit disk graphs
ترجمه فارسی عنوان
درختان کامل استینر در واحد گرافیکی دیسک یک ؟؟
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
الگوریتم های تقریبی، درخت کامل استینر، نمودار دیسک واحد
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Given an edge-weighted graph G=(V,E)G=(V,E) and a subset R of V, a Steiner tree of G is a tree which spans all the vertices in R. A full Steiner tree is a Steiner tree which has all the vertices of R as its leaves. The full Steiner tree problem is to find a full Steiner tree of G with minimum weight. In this paper we consider the full Steiner tree problem when G is a unit disk graph. We present a 20-approximation algorithm for the full Steiner tree problem in G. As for λ -precise unit disk graphs we present a (10+1λ)-approximation algorithm, where λ is the length of the shortest edge in G.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 48, Issue 6, August 2015, Pages 453–458
Journal: Computational Geometry - Volume 48, Issue 6, August 2015, Pages 453–458
نویسندگان
Ahmad Biniaz, Anil Maheshwari, Michiel Smid,