حل مساله رنگ آمیزی جمعی گراف با استفاده از الگوریتم ابتکاری
Publish Year: 1401
نوع سند: مقاله ژورنالی
زبان: Persian
View: 166
This Paper With 9 Page And PDF Format Ready To Download
- Certificate
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
JR_IJDCS-5-1_004
تاریخ نمایه سازی: 4 اردیبهشت 1402
Abstract:
رنگ آمیزی جمعی گراف، اختصاص اعداد طبیعی به رئوس یگ گراف ساده می باشد، طوری که مجموع اعداد اختصاص داده شده به رئوس گراف، کمینه گردد. مهمترین کاربرد آن در حوزره زمانبندی می باشد. برای این مساله که جزو مسائل NP-Hard می باشد، تاکنون حل دقیقی ارائه نشده است. لذا در این پژوهش، یک الگوریتم ابتکاری مرکب، بر مبنای ایده شناسایی مجموعه های مستقل رئوس گراف و اختصاص کوچکترین عدد طبیعی در دسترس، برای بزرگترین مجموعه مستقل، توسعه داده شده است. الگوریتم پیشنهادی، بر روی گراف های موجود در کتابخانه های معروف گراف هایی که به صورت تصادفی تولید شده اند، آزمایش شده است. نتایج، نشان دهنده کارایی الگوریتم ارائه شده می باشد.
Keywords:
Authors
مرتضی رجب زاده
استادیار، دانشکده مهندسی، مرکز آموزش عالی محالت، محالت، ایران.
امین محمدنژاد
محقق، دانشکده مهندسی، مرکز آموزش عالی محالت، محالت، ایران.
کوروش عشقی
استاد، دانشکده مهندسی صنایع، دانشگاه صنعتی شریف، تهران، ایران