CIVILICA We Respect the Science
(ناشر تخصصی کنفرانسهای کشور / شماره مجوز انتشارات از وزارت فرهنگ و ارشاد اسلامی: ۸۹۷۱)

گواهی نمایه سازی مقاله چند رنگ آمیزی پهنای باند در گراف مبتنی بر اتاماتای یادگیر سلولی

عنوان مقاله: چند رنگ آمیزی پهنای باند در گراف مبتنی بر اتاماتای یادگیر سلولی
شناسه (COI) مقاله: ACCSI14_139
منتشر شده در چهاردهمین کنفرانس سالانه انجمن کامپیوتر ایران در سال ۱۳۸۷
مشخصات نویسندگان مقاله:

علیرضا انعامی عراقی - دانشگاه مهندسی کامپیوتر دانشگاه آزاد اسلامی واحد فراهان
جواد اکبری ترکستانی - دانشگاه مهندسی کامپیوتر دانشگاه آزاد اسلامی واحد اراک
محمدرضا میبدی - دانشکده مهندسی کامپیوتر و فناوری اطلاعات دانشگاه صنعتی امیرکبیر تهر

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

کلمات کلیدی:
مساله چند رنگ آمیری گراف، مساله رنگ آمیزی پهنای باند گراف، اتاماتای یادگیر سلولی.

صفحه اختصاصی مقاله و دریافت فایل کامل: https://www.civilica.com/Paper-ACCSI14-ACCSI14_139.html