بررسی مسایل مکانیابی میانه روی گراف های خاص

در این مقاله به مطالعه و بررسی مسایل - p میانه کلاسیک روی گراف ها میپردازیم. فرض کنیدG=V,E یک گراف غیرجهتداربا تابع طول L:E +Rو وزنهای راسی نامنفی باشد. هدف مسایل - p میانه، تعیین مکان Pسرویس دهنده روی یالها یا راس های G می باشد بطوری که مجموع کوتاه ترین فواصل وزن دار از هر راس به نزدیکترین سرویس دهنده مینیمم گردد. ابتدامسیله مکان یابی -2 میانه رو کاکتوس گراف بیان میشود و یک الگوریتم با پیچیدگی زمانیO(n2)پیشنهاد می گردد که درآن n تعداد ریوس گراف میباشد و تکنیک این الگوریتم را برای حل مسیله -2میانه روی کاکتوس گراف با یک و دو یال بحرانی به کارمی بریم، در نهایت با یک مثال به طور کامل کاربرد الگوریتم پیشنهادی را تشریح میکنیم.

Keywords:

مسیله مکان یابی , مکان میانه سرویس دهنده ها , کاکتوس گرافها , آنالیز پیچیدگی