کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
414262 680868 2015 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On full Steiner trees in unit disk graphs
ترجمه فارسی عنوان
درختان کامل استینر در واحد گرافیکی دیسک یک ؟؟
کلمات کلیدی
الگوریتم های تقریبی، درخت کامل استینر، نمودار دیسک واحد
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

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
نویسندگان
, , ,