@article { author = {Rajaati Bavil Olyaei, M. and Hooshmandasl, M. R.}, title = {Generating Tree Decomposition of Graphs with Imperialist Competitive Algorithm for Use in Secret Sharing Scheme}, journal = {Electronic and Cyber Defense}, volume = {7}, number = {3}, pages = {105-111}, year = {2019}, publisher = {Imam Hussein University}, issn = {2322-4347}, eissn = {2980-8979}, doi = {}, abstract = {Secret sharing refers to methods of distributing a secret amongst a group of participants, each of whom is assigned with a share of the secret. The secret can be reconstructed only when a sufficient number, of possibly different types of shares are combined together. Different secret sharing methods have been      presented, such as secret sharing schemes based on dominating set and edge dominating set. In edge     dominating set method, it is required that all of the edge dominating sets are obtained for the graph, which is a NP-complete problem. All of the edge dominating sets can be easily obtained, using tree decomposition of the graph and dynamic programming. Although generating tree decomposition of a graph with finite treewidth can be solved in polynomial time, but it is shown to be NP-complete for general graphs. In this paper, to generate tree decompositions of general graphs, we use the notion of Imperialist Competitive   Algorithm (ICA) which can be applied in parallel. Therefore, the proposed method, in addition to being a new method for implementation of the secret sharing scheme, can reduce runtime by up to five percent in parallel.  }, keywords = {Secret Sharing,Edge dominating set,Tree decomposition,Imperialist Competitive Algorithm (ICA)}, title_fa = {ساخت تجزیه درختی گراف ها با استفاده از الگوریتم رقابت استعماری جهت استفاده در تسهیم راز}, abstract_fa = {تسهیم راز، یعنی به اشتراک گذاشتن داده محرمانه میان تعدادی شرکت‌کننده، به‌طوری‌که زیرمجموعه­های مشخصی (مجاز) از آنها قادر به بازیابی آن داده، باشند ولی زیرمجموعه­های غیرمجاز قادر به بازیابی اطلاعات مرتبط با آن نباشند. روش­های متعدد برای تسهیم راز ارائه شده است. از جمله این روش­ها، تسهیم راز مبتنی­بر مجموعه احاطه­گر و احاطه­گر یالی است. در روش مبتنی بر احاطه­گر یالی، نیاز است که تمام مجموعه­های احاطه­گر یالی برای گراف به­دست آید. یافتن تمام مجموعه­های احاطه­گر یالی برای گراف یک مسئله NP-کامل است. به­سادگی می­توان تمام مجموعه­های احاطه­گر یالی یک گراف داده شده را  با استفاده از تجزیه­ درختی گراف آن و الگوریتم برنامه­نویسی پویا به­­دست آورد. ساخت تجزیه درختی یک گراف با عرض درختی محدود، از زمان چندجمله­ای است.  اما در حالت کلی محاسبه عرض درختی و ساختن تجزیه درختی با حداقل عرض، یک مسئله NP-کامل است. هدف ما در این مقاله، استفاده از الگوریتم رقابت استعماری برای ساخت تجزیه درختی گراف­ها است که می­تواند به­صورت موازی پیاده­سازی شود. بنابراین، روش پیشنهادی علاوه­بر این که روش نوینی برای پیاده­سازی طرح تسهیم راز است، می­تواند زمان اجرارا در حالت موازی تا 5% کاهش دهد.}, keywords_fa = {تسهیم راز,مجموعه ی احاطه گر یالی,تجزیه ی درختی و الگوریتم رقابت استعماری.‏}, url = {https://ecdj.ihu.ac.ir/article_204721.html}, eprint = {https://ecdj.ihu.ac.ir/article_204721_23a8e5dd834b5bbb22b881358fa97026.pdf} }