دانلود ترجمه مقاله روش پایین به بالا و الگوریتم سریع برای مجموعه مستقل حداکثر (اسپرینگر 2010)

یک روش پایین به بالا و الگوریتم های سریع برای مجموعه مستقل حداکثر

A Bottom-Up Method and Fast Algorithms for max independent set

چکیده

1 مقدمه

2 روش پایین به بالا

3 اصلاح تجزیه و تحلیل موردی برای گراف‌های با درجه متوسط ۴

4 هنگامی که روش پایین به بالا، معیار و تسخیر را براورده می‌سازد: بهبودهای نهایی و یک الگوریتم در گراف‌های کلی

5 نتیجه‌گیری

منابع

چکیده
     در مقاله، ابتدا روش جدیدی به نام «روش پایین به بالا» را ارائه می‌دهیم که به طور غیر رسمی، بهبودی از پیچیدگی بدترین حالت برای نمونه‌های «پراکنده» به نمونه‌های «متراکم‌تر» را منتشر می‌کند و کاربردی ساده و در عین حال غیر بدیهی از آن را در مساله پوشش مجموعه مینیمم نشان می‌دهیم. سپس به مجموعه مستقل ماکسیمم می‌پردازیم. با پیروی از روش پایین به بالا، بهبودهای پیچیدگی بدترین حالت از گراف‌های با متوسط درجه d را در گراف‌های با متوسط درجه بالاتر از d منتشر می‌کنیم. در واقع، با استفاده از الگوریتم‌های برای مجموعه مستقل ماکسیمم در گراف‌های با درجه متوسط ۳، به بررسی مجموعه مستقل ماکسیمم در گراف‌های با درجه متوسط ۴، ۵ و ۶ می‌پردازیم. سپس تکنیک پایین به بالا را با تکنیک‌های معیارها و تسخیر به منظور بهبود زمان‌های اجرای گراف‌های با ماکسیمم درجه ۴، ۵ و ۶ و همچنین گراف‌های کلی ترکیب می‌کنیم. بهترین کرام‌های محاسباتی به دست آمده برای مجموعه مستقل ماکسیمم عبارتنداز: ، ، و برای گراف‌های با ماکسیمم درجه (یا با متوسط درجه کلی‌تر) به ترتیب ۴، ۵ و ۶، و برای گراف‌های عمومی. این نتایج بر اساس بهترین نتایج شناخته شده فضای چند جمله‌ای برای این موارد بهبود می‌یابند.

2 روش پایین به بالا
     در این بخش، روشی را ارائه می‌دهیم که بر دو مرحله تکیه دارد: ۱) انتخاب معیار پیچیدگی بازگشتی به کار رفته در روشی بسیار ساده در بخش ۲.۱. برای پوشش مجموعه مینیمم به منظور به دست آوردن کران‌های زمانی غیر بدیهی برای نمونه‌های مجموعه-کاردینالیته‌های متوسط کراندار، و ۲) روشی برای حصول اطمینان از این که در نمونه‌های با تراکم بیشتر از d، انشعاب خوبی (نسبت به معیار پیچدگی انتخاب شده) رخ می‌دهد. این نکته دوم در بخش ۲.۲ برای مجموعه مستقل ماکسیمم نشان داده می‌شود.

2.1. اهمیت معیار پیچیدگی بازگشتی: مورد پوشش مجموعه مینیمم
     اکنون مساله پوشش مجموعه مینیمم با مجموعه زمینه و سیستم مجموعه را در نظر می‌گیریم. نشان می‌دهیم که روش پایین به بالا به سادگی برای به دست آوردن کران‌های زمانی بهبود یافته برای نمونه با مجموعه‌های با متوسط (ماکسیمم) اندازه d، برای هر ، اعمال می‌شود. لم ۱. الگوریتم ارائه شده در [۹] پوشش مجموعه مینیمم را در زمان مربوطه ، ، و در نمونه‌های با مجموعه‌های اندازه متوسط به ترتیب ۵، ۶، ۷ و ۸ حل می‌کند.

     اثبات. تعداد مجموعه‌های با اندازه i را با ni و تعداد عناصر با فرکانس j را با mj نشان می‌دهیم. [۹] الگوریتمی را ارائه می‌دهد که در زمان کار می‌کند، که در اینجا . در اینجا wi، وزن مربوط به مجموعه‌ای با اندازهi است و vj وزن مربوط به عنصر با فرکانس j است. به سادگی مشاهده می‌شود که با استفاده از تحدب، اگر اندازه متوسط مجموعه‌ها عدد صحیح d باشد، در این صورت . علاوه‌براین توجه کنید که برای هر ، داریم ، از اینرو، . به دست می‌آوریم (اگر همه مجموعه‌ها دارای اندازه d و همه عناصر دارای فرکانس ۳ باشند، این کران کوچک یا دقیق است).