رنگ آمیزی گروندی خود تثبیت کننده با استفاده از نظریه بازی ها و یافتار مرتب سازی
سال انتشار: 1397
نوع سند: مقاله ژورنالی
زبان: فارسی
مشاهده: 374
فایل این مقاله در 10 صفحه با فرمت PDF قابل دریافت می باشد
- صدور گواهی نمایه سازی
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
JR_PADSA-6-2_005
تاریخ نمایه سازی: 30 فروردین 1399
چکیده مقاله:
خرابی گذرا در سیستم های توزیع شده در شرایط مختلفی مانند خرابی پردازه ها و حمله های امنیتی رخ می دهد. یک الگوریتم خود تثبیت کننده با شروع از هر حالت دلخواه، در زمان متناهی به حالت قانونی می رسد و در مقابل خرابی گذرا مقاوم است. در این مقاله، نخست، برای مسئله رنگ آمیزی گروندی، اولین الگوریتم قطعی خود تثبیت کننده مبتنی بر نظریه بازی ها را ارائه می کنیم. در این الگوریتم، که از قابلیت اجرا روی شبکه های ناشناس برخوردار است، برای کاهش تعداد رنگ های مصرفی، از یافتارهای مرتب سازی استفاده می کنیم. با به کارگیری تعادل نش، ثابت می کنیم که الگوریتم روی شبح مرکزی با پیچیدگی زمانی O(m) به رنگ آمیزی گروندی همگرا می شود که در آن m تعداد یال های شبکه است. نتایج شبیه سازی روی شبکه های مستقل از مقیاس، شبکه های تصادفی و شبکه های دنیای کوچک حاکی از آن است که به کارگیری یافتارهای مرتب سازی نسبت به عدم استفاده از آن ها موجب کاهش تعداد رنگ ها تا 18% و بهبود سرعت همگرایی به جواب تا 5% می گردد.
کلیدواژه ها:
نویسندگان
سید محمود طاهری
دانشگاه تهران
حسن حیدری
دانشگاه تهران
مراجع و منابع این مقاله:
لیست زیر مراجع و منابع استفاده شده در این مقاله را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود مقاله لینک شده اند :