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

نوع مقاله : مقاله پژوهشی

نویسندگان

بخش علوم کامپیوتر، دانشکده ریاضی، دانشگاه یزد

چکیده

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

کلیدواژه‌ها


   [1]      N. M. G. Al-Saidi and MM. Abdulhadi, “E--Voting System based on Secret Sharing Scheme,” Engineering and Technology, vol. 35(1), pp. 13-18, 2017.##
   [2]      C. Jing, H. Kun,  D. Ruiying, Z. Minghui, X. Yang, and Y. Quan, “Dominating set and network        coding-based routing in wireless mesh networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 26(2), pp. 423-433, 2015.##
   [3]      A. R. Mirghadri and F. S. Sangtajan, “An Efficient Visual Multi-Secret Sharing Scheme,” Electronical & Cyber Defence, vol. 3(4), pp. 1-9, 2016.(In Persian)##
   [4]      M. Rajaati, M. R. Hooshmandasl, M. Dinneen, and A. Shakiba, “On fixed-parameter tractability of the mixed domination problem for graphs with bounded tree-width,” Discrete Mathematics & Theoretical Computer Science, vol. 20(2), pp. 1-25, 2018.##
   [5]      M. Hashemipour, M. R. Hooshmandasl, and A. Shakiba, “On outer-connected domination for graph products,” arXiv preprint arXiv: 1708.00188, 2017.##
   [6]      H. L. Bodlaender, “A linear-time algorithm for finding tree-decompositions of small treewidth,” SIAM Journal on computing, vol. 25(6), pp.         1305–1317, 1996.##
   [7]      N. Robertson, and P. D. Seymour, “Graph minors. iii. plannar tree-width,” Combinatorial Theory, Series B, vol. 36(1), pp. 49–64, 1984.##
   [8]      B. Courcelle, “Fly-automata for checking monadic second-order properties of graphs of bounded tree-width,” Electronic Notes in Discrete Mathematics, vol. 50, pp. 3–8, 2015.##
   [9]      H. L. Bodlaender and B. V. A. Fluiter, “Reduction algorithms for graphs of small treewidth,” Information and Computation, vol. 167(2), pp. 86–119, 2001.##
[10]      H. L. Bodlaender, “Treewidth: Algorithmic techniques and results,” In International Symposium on Mathematical Foundations of Computer Science, Springer, pp. 19–36, 1997.##
[11]      F. Fomin, D. Kratsch, I. Todinca, and Y. Villanger, “Exact algorithms for treewidth and minimum         fill-in,” SIAM Journal on Computing, vol. 38(3), pp. 1058-1079, 2008.##
[12]      H. L. Bodlaender, P. G. Drange, M. S. Dregi, F. V. Fomin, D. Lokshtanov, and M. Pilipczuk, “A ckn 5-approximation algorithm for treewidth,” SIAM Journal on Computing, vol. 45(2), pp. 317–378, 2016.##
[13]      T. Hammerl, N. Musliu, and W. Schafhauser, “Metaheuristic algorithms and tree decomposition,” Springer Handbook of Computational Intelligence, pp. 1255-1270, 2015.##
 [14]      H. L. Bodlaender and A. M.C.A. Koster, “Treewidth computations I. Upper bounds,” Information and Computation, vol. 208, pp. 259–275, 2010.##
[15]      N. M. G. Al-Saidi, N. A. Rajab, M. R. Md Said, and K. A. Kadhim, “Perfect Secret Sharing based on Vertex  Dominating Set,” Computer Mathematics, Vol. 92(9), 2015.##
[16]      D. R. Stinson, “Decomposition Constructions for Secret Sharing Schemes,” IEEE, Transactions information theory, vol. 40(1), 1994.##
[17]      E. Atashpaz-Gargari and C. Lucas, “Imperialist Competitive Algorithm: An Algorithm for Optimization Inspired by Imperialistic Competition” IEEE Cong. Evol. Comput, Singapore, pp. 4661–4667, 2007.##