|
عنوان
|
حل مسأله رنگ آمیزی جمعی گراف با استفاده از الگوریتم ابتکاری
|
|
نوع پژوهش
|
مقاله چاپ‌شده
|
|
کلیدواژه‌ها
|
رنگ آمیزی جمعی گراف، مجموعه مستقل رئوس گراف، الگوریتم فراابتکاری
|
|
چکیده
|
رنگ آمیزی جمعی گراف، اختصاص اعداد طبیعی به رئوس یگ گراف ساده می باشد، طوری که مجموع اعداد اختصاص داده شده به رئوس گراف، کمینه گردد. مهمترین کاربرد آن در حوزره زمانبندی می باشد. برای این مسأله که جزو مسائل NP-Hard می باشد، تاکنون حل دقیقی ارائه نشده است. لذا در این پژوهش، یک الگوریتم ابتکاری مرکب، بر مبنای ایده شناسایی مجموعه های مستقل رئوس گراف و اختصاص کوچکترین عدد طبیعی در دسترس، برای بزرگترین مجموعه مستقل، توسعه داده شده است. الگوریتم پیشنهادی، بر روی گراف های موجود در کتابخانه های معروف گراف هایی که به صورت تصادفی تولید شده اند، آزمایش شده است. نتایج، نشان دهنده کارایی الگوریتم ارائه شده می باشد.
|
|
پژوهشگران
|
کوروش عشقی (نفر سوم)، امین محمدنژاد (نفر دوم)، مرتضی رجب زاده (نفر اول)
|