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

سال انتشار: 1398
نوع سند: مقاله ژورنالی
زبان: فارسی
مشاهده: 332

فایل این مقاله در 7 صفحه با فرمت PDF قابل دریافت می باشد

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این مقاله:

شناسه ملی سند علمی:

JR_PADSA-7-3_010

تاریخ نمایه سازی: 3 دی 1398

چکیده مقاله:

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

کلیدواژه ها:

تسهیم راز ، مجموعه ی احاطه گر یالی ، تجزیه ی درختی و الگوریتم رقابت استعماری.

نویسندگان

میثم رجعتی باویل علیایی

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

محمد رضا هوشمند اصل

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

مراجع و منابع این مقاله:

لیست زیر مراجع و منابع استفاده شده در این مقاله را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود مقاله لینک شده اند :
  • N. M. G. Al-Saidi and MM. Abdulhadi, E--Voting System based ...
  • C. Jing, H. Kun,  D. Ruiying, Z. Minghui, X. Yang, ...
  • A. R. Mirghadri and F. S. Sangtajan, An Efficient Visual ...
  • M. Rajaati, M. R. Hooshmandasl, M. Dinneen, and A. Shakiba, ...
  • M. Hashemipour, M. R. Hooshmandasl, and A. Shakiba, On outer-connected ...
  • H. L. Bodlaender, A linear-time algorithm for finding tree-decompositions of ...
  • N. Robertson, and P. D. Seymour, Graph minors. iii. plannar ...
  • B. Courcelle, Fly-automata for checking monadic second-order properties of graphs ...
  • H. L. Bodlaender and B. V. A. Fluiter, Reduction algorithms ...
  • H. L. Bodlaender, Treewidth: Algorithmic techniques and results, In International ...
  • F. Fomin, D. Kratsch, I. Todinca, and Y. Villanger, Exact ...
  • H. L. Bodlaender, P. G. Drange, M. S. Dregi, F. ...
  • T. Hammerl, N. Musliu, and W. Schafhauser, Metaheuristic algorithms and ...
  • H. L. Bodlaender and A. M.C.A. Koster, Treewidth computations I. ...
  • N. M. G. Al-Saidi, N. A. Rajab, M. R. Md ...
  • D. R. Stinson, Decomposition Constructions for Secret Sharing Schemes, IEEE, ...
  • E. Atashpaz-Gargari and C. Lucas, Imperialist Competitive Algorithm: An Algorithm ...
  • نمایش کامل مراجع