دراسة عملية لخوارزميات تقريبية لمسألة البيان الجزئي الأصغري الممتد المضاعف الترابط للمجموعة T

الملخص

مسألة إيجاد بيان جزئي أصغري ممتد مضاعف الترابط للمجموعة T هي مسألة مهمة في علوم الحاسب نظراً لتطبيقاتها الواسعة وأهميتها في مجال تصميم الطرق وإعادة توجيه حركة المرور في حال وجود نقاط مفصلية قوية او حوادث او مناطق اخلاء.

يمتاز البيان الجزئي الأصغري الممتد المضاعف الترابط للمجموعة T بقدرته على الحفاظ على خواص الاتصال بقوة في حال حدوث عطل في وصلة وفي حال حدوث عطل في عقدة من مجموعة عقد T. وعلى الرغم من كون مسألة إيجاد هذا النوع من البيانات الجزئيّة هو مسألة NP-complete. فإنّ من الممكن إيجاد حلول تقريبيّة من خلال خوارزميات تقريبيّة وفعالة. وهذا ما سنركز عليه خلال هذا البحث.