دانلود کتاب A better constant-factor approximation for weighted dominating set in unit disk graph

Name: A better constant-factor approximation for weighted dominating set in unit disk graph
Availability: InStock
Author: Huang Y.

by Huang Y., Gao X., Zhang Z.

عنوان فارسی: تقریب بهتری ثابت عامل برای بازی وزن را در نمودار دیسک واحد
سال: 2008
زبان: انگلیسی
تعداد صفحه (نسخه چاپی - نسخه الکترونیکی): 16-16
نوع فایل: PDF دانلود نرم افزار مطالعه
حجم: 0.41 مگابایت

گزارش تخلف

دانلود کتاب

افزودن خلاصه فارسی

جزییات کتاب

This paper presents a (10 + ε)-approximation algorithm to compute minimum-weight connected dominating set (MWCDS) in unit disk graph. MWCDS is to select a vertex subset with minimum weight for a given unit disk graph, such that each vertex of the graph is contained in this subset or has a neighbor in this subset. Besides, the subgraph induced by this vertex subset is connected. Our algorithm is composed of two phases: the first phase computes a dominating set, which has approximation ratio 6 + ε (ε is an arbitrary positive number), while the second phase connects the dominating sets computed in the first phase, which has approximation ratio 4.

گزارش اشکال ⚠