کتاب الکترونیکی

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

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

دانلود کتاب A better constant-factor approximation for weighted dominating set in unit disk graph (به فارسی: یک تقریب ضریب ثابت بهتر برای مجموعه غالب وزنی در نمودار واحد دیسک) نوشته شده توسط «Huang Y. – Gao X. – Zhang Z.»

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

موضوع اصلی: 1

نوع: کتاب الکترونیکی

نویسنده: Huang Y. – Gao X. – Zhang Z.

زبان: English

فرمت کتاب: pdf (قابل تبدیل به سایر فرمت ها)

سال انتشار: 2008

تعداد صفحه: 16

حجم کتاب: 1 مگابایت

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

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

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.

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

مبلغی که بابت خرید کتاب می‌پردازیم به مراتب پایین‌تر از هزینه‌هایی است که در آینده بابت نخواندن آن خواهیم پرداخت.
برچسب ها
مبلغی که بابت خرید کتاب می‌پردازیم به مراتب پایین‌تر از هزینه‌هایی است که در آینده بابت نخواندن آن خواهیم پرداخت.
کتابخانه دیجیتال بَلیان