پایان نامه > کتابخانه مرکزی دانشگاه صنعتی شاهرود > علوم ریاضی > مقطع کارشناسی ارشد > سال 1395
پدیدآورندگان:
ماهیه پقه [پدیدآور اصلی]، [استاد راهنما]، جعفر فتحعلی[استاد مشاور]
چکیده: مدل قابلیت اطمینان از مسائل مکانیابی، با موقعیت‌هایی که سرویس‌دهنده‌ها ممکن است از کار بیفتند، سر‌وکار دارد. در این صورت مشتری‌های مختص سرویس‌دهنده‌ی مذکور باید از دیگر سرویس‌دهنده‌های در حال کار خدمات دریافت کنند. ونگ و همکارانش مدلی براساس قابلیت اطمینان پیشنهاد داده‌اند که در آن هر سرویس‌دهنده با احتمال مشخصی‏ (مانند ρ‎) ممکن است از کار بیفتد. زمانی که سرویس‌دهنده‌ای از کار می‌افتد سرویس‌دهنده‌های دیگر پاسخگوی تمام تقاضاها هستند. با فرض اینکه سرویس‌دهنده‌ها هم‌زمان از کار نمی‌افتند ونگ و همکارانش مساله پشتیبان ‎2-‎مرکز روی درخت را در نظر گرفتند. این مساله عبارت است از یافتن محل استقرار دو سرویس‌دهنده‌ روی راس‌ها به گونه‌ای که امید طولانی‌ترین فاصله از هر راس تا نزدیک‌ترین سرویس‌دهنده‌ی در حال کار مینیمم گردد. هدف ما در این تحقیق مطالعه‌ی مساله پشتیبان ‎2-‎مرکز روی برخی از گراف‌ها نظیر گراف‌های بازه‌ای،‏درخت‌ها‏، دورها، مسیرها، گراف‌های تک‌دوری است. با ارائه‌ی الگوریتم‌هایی نشان می‌دهیم این مسأله روی مسیر، درخت، دور و گراف تک‌دوری به ترتیب با پیچیدگی زمانی O(n)، O(n log⁡n)، O(n^2) و O(n^2 log⁡ n) ‎ قابل حل است.
کلید واژه ها (نمایه ها):
#پشتیبان 2-مرکز‏ #گراف بازه‌ای‏ #مسیر‏ #درخت‏ #دور
محل نگهداری: کتابخانه مرکزی دانشگاه صنعتی شاهرود
یادداشت: حقوق مادی و معنوی متعلق به دانشگاه صنعتی شاهرود می باشد.
تعداد بازدید کننده:
پایان نامه های مرتبط (بر اساس کلیدواژه ها)