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

ترجمه فارسی توضیحات (ترجمه ماشینی)

یک تقریب ضریب ثابت بهتر برای مجموعه غالب وزنی در نمودار واحد دیسک

این مقاله یک الگوریتم تقریبی (10 + ε) را برای محاسبه مجموعه غالب متصل با حداقل وزن (MWCDS) در نمودار واحد دیسک ارائه می‌کند. MWCDS عبارت است از انتخاب یک زیرمجموعه راس با حداقل وزن برای یک گراف دیسک واحد معین، به طوری که هر رأس نمودار در این زیرمجموعه وجود داشته باشد یا یک همسایه در این زیر مجموعه داشته باشد. علاوه بر این، زیرگراف القا شده توسط این زیر مجموعه راس متصل است. الگوریتم ما از دو فاز تشکیل شده است: فاز اول یک مجموعه غالب را محاسبه می کند که دارای نسبت تقریبی 6 + ε است (ε یک عدد مثبت دلخواه است)، در حالی که فاز دوم مجموعه های غالب محاسبه شده در فاز اول را که دارای نسبت تقریبی است، به هم متصل می کند. 4.

A better constant-factor approximation for weighted dominating set in unit disk graph

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.