فهرست نشریات علمی دسترسی آزاد ایران

در سال‌های اخیر معکوس مسائل مکان‌یابی روی شبکه‌ها موضوع تعداد زیادی از تحقیقات بوده است. مسئله مکان‌یابی 1-مرکز مطلق در یک شبکه عبارت است از یافتن یک نقطه روی شبکه به عنوان سرویس‌دهنده به طوری که فاصله دورترین نقطه روی گراف تا سرویس‌دهنده حداقل شود. در این مقاله به بررسی معکوس مسئله مکان‌یابی 1-مرکز مطلق روی یک گراف دور بدون وزن می‌پردازیم. یک گراف دور یک مسیر بسته است به طوری که درجه هر راس گراف 2 است. در معکوس مسئله مکان‌یابی 1-مرکز مطلق روی یک گراف دور یک راس در گراف مشخص شده است و هدف این است تا طول یال‌های گراف دور را افزایش دهیم به طوری که با انجام کمترین هزینه راس مشخص شده با طول یال‌های جدید یک 1-مرکز مطلق گراف دور باشد. در این مقاله یک الگوریتم ترکیبیاتی برای حل این مسئله پیشنهاد می‌کنیم به طوری که پیچیدگی زمانی الگوریتم برای گراف‌های دور با راس خواهد بود.