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

Abstract

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