Title : ( ارائه یک الگوریتم تقریبی حریصانه برای رنگ آمیزی گراف ها )
Authors: Mostafa Tavakoli , Khatere Ghorbani Moghadam ,
دانلود فایل برای اعضای دانشگاهAccess to full-text not allowed by authors
Abstract
مسئله رنگ‌آمیزی گراف ( ) یک مسئله بهینه‌سازی ترکیباتی است و مشخص کردن عدد رنگی یک مسئله‌ی است زیرا همانطور که تعداد رئوس و یال‌ها در گراف افزایش می‌یابد پیچیدگی مسئله نیز افزایش می‌یابد چون هر الگوریتم عدد رنگی نمونه را نمی‌تواند پیدا کند و زمان اجرای هر الگوریتم برای هر نمونه می‌تواند متفاوت باشد و به همین دلیل الگوریتم‌های تقریبی بسیاری ارائه شده است که از نظر زمان اجرا و جواب برای گراف‌های معیار واقع در کتابخانه با هم مقایسه شده‌اند. مسئله رنگ‌آمیزی گراف کاربردهای زیادی در میدان‌های متفاوتی مانند حل مسائل بیولوژیکی، ارتباطات و اینترنت دارد و همچنین برای کاربردهای مهندسی و مسائل واقعی جهان استفاده می‌شود. به دلیل اهمیت به‌دست آوردن جواب‌های بهتر برای مسئله رنگ‌آمیزی گراف تعداد الگوریتم‌هایی که جواب تقریبی می‌دهند مانند الگوریتم‌های ابتکاری، فراابتکاری و حریصانه افزایش یافت. هدف ما ارائه یک الگوریتم تقریبی برای رنگ‌آمیزی گراف می‌باشد که جواب‌ها را بهبود دهد و زمان اجرا را کاهش دهد و برای نشان دادن بهبود این الگوریتم، آن را در نرم‌افزار متلب پیاده‌سازی و بر روی نمون‌ّهایی از گراف‌های معیار اجرا می‌کنیم و کارآیی الگوریتم خودمان را با بهترین الگوریتم‌های موجود مقایسه می‌کنیم.
Keywords
, عددرنگی, الگوریتم‌های حریصانه رنگ‌آمیزی, درجه‌ی رأس
@inproceedings{paperid:1096849,
author = {Tavakoli, Mostafa and خاطره قربانی مقدم},
title = {ارائه یک الگوریتم تقریبی حریصانه برای رنگ آمیزی گراف ها},
booktitle = {شانزدهمین کنفرانس بین المللی انجمن ایرانی تحقیق در عملیات},
year = {2023},
location = {IRAN},
keywords = {عددرنگی، الگوریتم‌های حریصانه رنگ‌آمیزی، درجه‌ی رأس},
}
%0 Conference Proceedings
%T ارائه یک الگوریتم تقریبی حریصانه برای رنگ آمیزی گراف ها
%A Tavakoli, Mostafa
%A خاطره قربانی مقدم
%J شانزدهمین کنفرانس بین المللی انجمن ایرانی تحقیق در عملیات
%D 2023
