شماره ركورد كنفرانس :
5432
عنوان مقاله :
ارايه يك الگوريتم تقريبي حريصانه براي رنگ‌آميزي گراف‌ها
پديدآورندگان :
موسوي حنيفه hmousv@gmail.com دانشجوي دكتري رياضي، دانشگاه فردوسي مشهد , توكلي مصطفي m_tavakoli@ferdowsi.um.ac.ir عضو هيئت علمي دانشكده علوم رياضي، دانشگاه فردوسي مشهد , قرباني مقدم خاطره kh.ghorbani@khu.ac.ir عضو هيئت علمي موسسه تحقيقات رياضي دكتر غلامحسين مصاحب، دانشگاه خوارزمي
كليدواژه :
عددرنگي , الگوريتم‌هاي حريصانه رنگ‌آميزي , درجه‌ي رأس.
عنوان كنفرانس :
شانزدهمين كنفرانس بين المللي انجمن ايراني تحقيق در عمليات
چكيده فارسي :
مسئله رنگ‌آميزي گراف ( ) يك مسئله بهينه‌سازي تركيباتي است و مشخص كردن عدد رنگي يك مسئله‌ي است زيرا همانطور كه تعداد رئوس و يال‌ها در گراف افزايش مي‌يابد پيچيدگي مسئله نيز افزايش مي‌يابد چون هر الگوريتم عدد رنگي نمونه را نمي‌تواند پيدا كند و زمان اجراي هر الگوريتم براي هر نمونه مي‌تواند متفاوت باشد و به همين دليل الگوريتم‌هاي تقريبي بسياري ارائه شده است كه از نظر زمان اجرا و جواب براي گراف‌هاي معيار واقع در كتابخانه با هم مقايسه شده‌اند. مسئله رنگ‌آميزي گراف كاربردهاي زيادي در ميدان‌هاي متفاوتي مانند حل مسائل بيولوژيكي، ارتباطات و اينترنت دارد و همچنين براي كاربردهاي مهندسي و مسائل واقعي جهان استفاده مي‌شود. به دليل اهميت به‌دست آوردن جواب‌هاي بهتر براي مسئله رنگ‌آميزي گراف تعداد الگوريتم‌هايي كه جواب تقريبي مي‌دهند مانند الگوريتم‌هاي ابتكاري، فراابتكاري و حريصانه افزايش يافت. هدف ما ارائه يك الگوريتم تقريبي براي رنگ‌آميزي گراف مي‌باشد كه جواب‌ها را بهبود دهد و زمان اجرا را كاهش دهد و براي نشان دادن بهبود اين الگوريتم، آن را در نرم‌افزار متلب پياده‌سازي و بر روي نمونه‌هايي از گراف‌هاي معيار اجرا مي‌كنيم و كارآيي الگوريتم خودمان را با بهترين الگوريتم‌هاي موجود مقايسه مي‌كنيم.
