محبوبترین نویسندگان :
نویسندگان مقالات پربازدید :
چهل و ششمین کنفرانس ریاضی ایران
جزئیات رویداد
همایش ، رویداد ، ژورنال
اینستاگرام تی پی بین
حوزه های تحت پوشش رویداد

  • یافتن آلفا جورسازی رنگی با استفاده از الگوریتم موازی پیشنهادی

    نویسندگان :
    کلمات کلیدی :
    جزئیات بیشتر مقاله
    • تاریخ ارائه: 1394/01/01
    • تاریخ انتشار در تی پی بین: 1394/01/01
    • تعداد بازدید: 485
    • تعداد پرسش و پاسخ ها: 0
    • شماره تماس دبیرخانه رویداد: -
    در این مقاله ما دو مفهوم ماکزیمم جورسازی رنگی و رنگ آمیزی یال ها را با هم ترکیب نموده و مفهوم جدیدی به نام آلفا جورسازی رنگی را ارائه داده ایم. در یک گراف ساده با این ویژگی که هر یال قابلیت این را دارد که رنگ های خاصی را به خود اختصاص دهد. منظور از آلفا جورسازی رنگی، بیشترین تعداد رنگ های مجازی است که می توان به یال ها اختصاص داد، به شرطی که هیچ کدام از یال های متصل به یک گره هم رنگ نباشند و تعداد یال های رنگ شده ی هر رنگ نسبت به ماکزیمم جورسازی آن رنگ آلفا برابر باشد. بنابراین هدف ما در این مقاله یافتن آلفا جورسازی رنگی است. برای حل این مسئله از رویکرد کلاس بندی یال ها استفاده می نماییم. هر کلاس، بیانگر یال هایی است که می توانند رنگ های یکسانی به خود اختصاص دهند. بر مبنای کلاس بندی و ترتیبی که برای رنگ کردن یال ها در نظر می گیریم، الگوریتم موازی به نام pαmc ارائه داده ایم که مسئله ی آلفا جورسازی رنگی را به صورت بازگشتی حل می کند. هر یک از پردازنده ها برای ماکزیمم سازی جورسازی به یافتن طولانی ترین مسیر می پردازد تا بتواند ماکزیمم تعداد رنگ ها را رنگ آمیزی نماید. نشان خواهیم داد با تعیین تعداد پردازنده ها یکی کمتر از تعداد رنگ ها به بهره وری حدود 90 درصد دست یافته ایم.

سوال خود را در مورد این مقاله مطرح نمایید :

با انتخاب دکمه ثبت پرسش، موافقت خود را با قوانین انتشار محتوا در وبسایت تی پی بین اعلام می کنم
مقالات جدیدترین رویدادها
مقالات جدیدترین ژورنال ها