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

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

عنوان مقاله: حل مسأله رنگ آمیزی در گراف با استفاده از اتوماتای یادگیر سلولی
شناسه (COI) مقاله: ACCSI14_044
منتشر شده در چهاردهمین کنفرانس سالانه انجمن کامپیوتر ایران در سال 1387
مشخصات نویسندگان مقاله:

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

خلاصه مقاله:
مسأله رنگ آمیزی گراف عبارت است از انتساب K رنگ به رأس های یک گراف به صورت یکه هیچ دو رأس مجاور در گراف دارای رنگ یکسانی نباشند . کمترین تعداد رنگی که بتوان یک گراف را با آن تعداد رنگ , رنگ آمیزی کرد , عدد رنگی گراف نامیده می شود. مسأله رنگ آمیزی گراف از جمله مسایل NP-complete می باشد و به همین دلیل الگوریتم های تقریبی متعددی برای آن طراحی شده است . در این مقاله با استفاده از اتوماتای یادگیر سلولی نامنظم سه الگوریتم تقریبی برای حل مسأله رنگ آمیزی گراف پیشنهاد می شود. الگوریتم های تقریبی پیشنهادی با الگوریتم های تقریبی بلام , کارگر و هالپرین مقایسه شده است . طبق آزمایش های انجام گرفته الگوریتم های پیشنهادی نتایج بهتری را در مقایسه با الگوریتم های فوق الذکر تولید می کنند.

کلمات کلیدی:
رنگ آميزي گراف، الگوريتم هاي تقريبي,اتوماتاي يادگير سلولي

صفحه اختصاصی مقاله و دریافت فایل کامل: https://civilica.com/doc/60792/