الگوريتم هاي بهينه براي مدل هاي مكان‌يابي 2 مركز ناخوشايند پشتيبان روي گراف هاي درختي

The Optimal Algorithms for Backup Undesirable 2Center Location Models on Tree Graphs

در اين مقاله به مطالعه و بررسي مسايل مكان يابي 2 - مركز ناخوشايند پشتيبان روي گراف هاي درختي پرداخته ميشود. هدف پيدا كردن بهترين مكان روي مجموعه راسي درخت داده شده جهت تاسيس دو سرويس دهنده ي ناخوشايند ميباشد به طوريكه نزديكترين فاصله ي مورد انتظار بين مشتريان موجود و سرويس دهنده هاي فعال ماكزيمم گردد با فرض آنكه هر سرويس دهنده ممكن است با يك احتمال مشخص از ارايه ي خدمات قصور نموده و در اينصورت سرويس دهنده فعال ديگر بايد به تمامي مشتريان روي سيستم خدمت دهي نمايد. الگوريتم هاي تركيبياتي دقيق با پيچيدگي هاي زماني و براي بهدست آوردن جواب هاي بهينه دو نوع مدل خاص طراحي و پيشنهاد ميگردند به طوريكه نشان دهنده ي تعداد راس هاي گراف درختي داده شده ميباشد.

In this paper, we investigate the backup undesirable center location models on tree graphs. The aim is to obtain the best locations on the vertex set of the underlying tree for establishing two undesirable servers so that the expected value of the closest distance from the existing customers to the functioning facilities is maximized under the assumption that any facility may fail with a given probability and in this case the other active server must serve all the customers. The exact combinatorial algorithms with andtime complexities are developed for obtaining the optimal solutions of two certain models, where is the number of the vertices in the given tree graph.