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

یک الگوریتم تقریبی 2 1/10 برای تعمیم مسئله مجموعه ای از لبه های وزن دار

A 2 1/10-Approximation Algorithm for a Generalization of the Weighted Edge-Dominating Set Problem

دانلود کتاب A 2 1/10-Approximation Algorithm for a Generalization of the Weighted Edge-Dominating Set Problem (به فارسی: یک الگوریتم تقریبی 2 1/10 برای تعمیم مسئله مجموعه ای از لبه های وزن دار) نوشته شده توسط «Carr R.»

اطلاعات کتاب یک الگوریتم تقریبی 2 1/10 برای تعمیم مسئله مجموعه ای از لبه های وزن دار

موضوع اصلی: الگوریتم ها و ساختارهای داده

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

نویسنده: Carr R.

زبان: English

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

سال انتشار: 2001

تعداد صفحه: 10

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

توضیحات کتاب یک الگوریتم تقریبی 2 1/10 برای تعمیم مسئله مجموعه ای از لبه های وزن دار

ما تقریب‌پذیری مسئله مجموعه وزن‌دار بر لبه را مطالعه می‌کنیم. اگرچه حتی حالت وزن‌نشده NP-Complete است، در این مورد یک راه‌حل با اندازه حداکثر دو برابر حداقل را می‌توان به‌دلیل رابطه نزدیک آن با حداقل تطابق حداکثری، به طور مؤثر محاسبه کرد. با این حال، در مورد وزن، چنین رابطه خوبی وجود ندارد. در این مقاله، پس از اینکه نشان دادیم تسلط لبه وزنی به اندازه مشکل پوشش راس وزنی به خوبی مورد مطالعه قرار گرفته برای تقریب دشوار است، ما یک استراتژی طبیعی را در نظر می گیریم که مجموعه ای از لبه غالب را به پوشش لبه کاهش می دهد.

We study the approximability of the weighted edge-dominating set problem. Although even the unweighted case is NP-Complete, in this case a solution of size at most twice the minimum can be efficiently computed due to its close relationship with minimum maximal matching; however, in the weighted case such a nice relationship is not known to exist. In this paper, after showing that weighted edge domination is as hard to approximate as the well studied weighted vertex cover problem, we consider a natural strategy, reducingedge-dominating set to edge cover.

دانلود کتاب «یک الگوریتم تقریبی 2 1/10 برای تعمیم مسئله مجموعه ای از لبه های وزن دار»

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