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

قیمت خرید این محصول

۳۳,۰۰۰ تومان

دانلود مقاله انگلیسی

عنوان فارسی

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

عنوان انگلیسی

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

صفحات مقاله فارسی

19

صفحات مقاله انگلیسی

12

سال انتشار

2010

رفرنس

دارای رفرنس در داخل متن و انتهای مقاله

نشریه

اشپرینگر - Springer

فرمت مقاله انگلیسی

PDF

فرمت ترجمه مقاله

pdf و ورد تایپ شده با قابلیت ویرایش

فونت ترجمه مقاله

بی نازنین

سایز ترجمه مقاله

14

نوع مقاله

ISI

نوع ارائه مقاله

کنفرانس

کد محصول

12452

وضعیت ترجمه عناوین تصاویر و جداول

ترجمه شده است ✓

وضعیت ترجمه متون داخل تصاویر و جداول

ترجمه شده است ✓

وضعیت ترجمه منابع داخل متن

به صورت عدد درج شده است ✓

وضعیت فرمولها و محاسبات در فایل ترجمه

به صورت عکس، درج شده است ✓

ضمیمه

ندارد ☓

بیس

نیست ☓

مدل مفهومی

ندارد ☓

پرسشنامه

ندارد ☓

متغیر

ندارد ☓

فرضیه

ندارد ☓

رفرنس در ترجمه

در انتهای مقاله درج شده است

رشته های مرتبط با این مقاله

مهندسی کامپیوتر

گرایش های مرتبط با این مقاله

مهندسی الگوریتم ها و محاسبات - مهندسی نرم افزار

کلمات کلیدی

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

کلمات کلیدی انگلیسی

Bottom-Up Method - Max Independent Set - Exact Algorithms

doi یا شناسه دیجیتال

https://doi.org/https://doi.org/10.1007/978-3-642-13731-0_7

فهرست مطالب

چکیده
1. مقدمه
2. روش پایین به بالا
3. اصلاح تجزیه و تحلیل موردی برای گراف‌های با درجه متوسط ۴
4. هنگامی که روش پایین به بالا، معیار و تسخیر را براورده می‌سازد: بهبودهای نهایی و یک الگوریتم در گراف‌های کلی
5. نتیجه‌گیری
منابع

تصاویر فایل ورد ترجمه مقاله (جهت بزرگنمایی روی عکس کلیک نمایید)

نمونه چکیده ترجمه متن فارسی

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

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

اهمیت معیار پیچیدگی بازگشتی: مورد پوشش مجموعه مینیمم
اکنون مساله پوشش مجموعه مینیمم با مجموعه زمینه و سیستم مجموعه را در نظر می‌گیریم. نشان می‌دهیم که روش پایین به بالا به سادگی برای به دست آوردن کران‌های زمانی بهبود یافته برای نمونه با مجموعه‌های با متوسط (ماکسیمم) اندازه d، برای هر ، اعمال می‌شود.

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

برچسب‌ها: دانلود رایگان مقالات انگلیسی مهندسی کامپیوتر