حل مسأله رنگ آمیزی در گراف با استفاده از اتوماتای یادگیر سلولی
Publish place: 14th Annual Conference of Computer Society of Iran
Publish Year: 1387
نوع سند: مقاله کنفرانسی
زبان: Persian
View: 2,385
متن کامل این Paper منتشر نشده است و فقط به صورت چکیده یا چکیده مبسوط در پایگاه موجود می باشد.
توضیح: معمولا کلیه مقالاتی که کمتر از ۵ صفحه باشند در پایگاه سیویلیکا اصل Paper (فول تکست) محسوب نمی شوند و فقط کاربران عضو بدون کسر اعتبار می توانند فایل آنها را دریافت نمایند.
- Certificate
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
ACCSI14_044
تاریخ نمایه سازی: 26 مهر 1387
Abstract:
مسأله رنگ آمیزی گراف عبارت است از انتساب K رنگ به رأس های یک گراف به صورت یکه هیچ دو رأس مجاور در گراف دارای رنگ یکسانی نباشند . کمترین تعداد رنگی که بتوان یک گراف را با آن تعداد رنگ , رنگ آمیزی کرد , عدد رنگی گراف نامیده می شود. مسأله رنگ آمیزی گراف از جمله مسایل NP-complete می باشد و به همین دلیل الگوریتم های تقریبی متعددی برای آن طراحی شده است . در این مقاله با استفاده از اتوماتای یادگیر سلولی نامنظم سه الگوریتم تقریبی برای حل مسأله رنگ آمیزی گراف پیشنهاد می شود. الگوریتم های تقریبی پیشنهادی با الگوریتم های تقریبی بلام , کارگر و هالپرین مقایسه شده است . طبق آزمایش های انجام گرفته الگوریتم های پیشنهادی نتایج بهتری را در مقایسه با الگوریتم های فوق الذکر تولید می کنند.
Keywords:
Authors
مهدی عنایت زارع
مجتمع آموزش عالی جندی شاپور دزفول ایران
محمدرضا میبدی
دانشگاه صنعتی امیرکبیر دانشکده مهندسی کامپیوتر و فناوری اطلاعات، ته