ساخت تجزيه درختي گراف ها با استفاده از الگوريتم رقابت استعماري جهت استفاده در تسهيم راز

تسهيم راز، يعني به اشتراك گذاشتن داده محرمانه ميان تعدادي شركت‌كننده، به‌طوري‌كه زيرمجموعه هاي مشخصي (مجاز) از آنها قادر به بازيابي آن داده، باشند ولي زيرمجموعه هاي غيرمجاز قادر به بازيابي اطلاعات مرتبط با آن نباشند. روش هاي متعدد براي تسهيم راز ارائه شده است. از جمله اين روش ها، تسهيم راز مبتني بر مجموعه احاطه گر و احاطه گر يالي است. در روش مبتني بر احاطه گر يالي، نياز است كه تمام مجموعه هاي احاطه گر يالي براي گراف به دست آيد. يافتن تمام مجموعه هاي احاطه گر يالي براي گراف يك مسئله NPكامل است. به سادگي مي توان تمام مجموعه هاي احاطه گر يالي يك گراف داده شده را  با استفاده از تجزيه درختي گراف آن و الگوريتم برنامه نويسي پويا به دست آورد. ساخت تجزيه درختي يك گراف با عرض درختي محدود، از زمان چندجمله اي است.  اما در حالت كلي محاسبه عرض درختي و ساختن تجزيه درختي با حداقل عرض، يك مسئله NPكامل است. هدف ما در اين مقاله، استفاده از الگوريتم رقابت استعماري براي ساخت تجزيه درختي گراف ها است كه مي تواند به صورت موازي پياده سازي شود. بنابراين، روش پيشنهادي علاوه بر اين كه روش نويني براي پياده سازي طرح تسهيم راز است، مي تواند زمان اجرارا در حالت موازي تا 5% كاهش دهد.