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

رجعتی باویل علیایی, میثم; هوشمند اصل, محمد رضا

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

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

نویسندگان

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

چکیده

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

کلیدواژه‌ها

عنوان مقاله [English]

Generating Tree Decomposition of Graphs with Imperialist Competitive Algorithm for Use in Secret Sharing Scheme

نویسندگان [English]

M. Rajaati Bavil Olyaei
M. R. Hooshmandasl

Department of Computer Science, Faculty of Mathematics Science, Yazd University

چکیده [English]

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.

کلیدواژه‌ها [English]

Secret Sharing
Edge dominating set
Tree decomposition
Imperialist Competitive Algorithm (ICA)

مراجع

[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 c^kn 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.##