یک الگوریتم حریصانه برای ساخت پوشاننده هندسی تحمل‌پذیر ناحیه-خطا

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

نویسندگان

1 استادیار، گروه علوم کامپیوتر، دانشگاه بجنورد، بجنورد، ایران

2 دانشیار، دانشکده علوم ریاضی، دانشگاه یزد، یزد، ایران

چکیده

در این مقاله، مسئله ساخت پوشاننده هندسی تحمل‌پذیر ناحیه-خطا مقید به زیر کلاسی از نواحی محدب، مورد بحث قرار می‌گیرد. فرض کنید که S مجموعه‌ای از n نقطه در صفحه باشد. به طور دقیق‌تر، در این مقاله، یک الگوریتم حریصانه برای ساخت پوشاننده هندسی تحمل-پذیر ناحیه-خطا در حالتی که ناحیه‌های خطا، مجموعه ای از نیم صفحه ها با مرز موازی با حداکثر k خط است، بررسی می‌شود. نشان داده می‌شود که پیچیدگی زمانی الگوریتم پیشنهادی O(kn^3 log⁡n) و گراف تولید شده توسط آن دارای O(kn) یال است. طبق آخرین اطلاعاتی که داریم بهترین الگوریتمی که برای ساخت یک پوشاننده هندسی تحمل‌پذیر ناحیه-خطا برای مجموعه نقطه S ارائه شده است، دارای زمان اجرای O(n log^2⁡n) است و گراف تولید شده توسط آن دارای O(n log⁡n) یال است.

کلیدواژه‌ها


Smiley face

[1] A. B. Dehkordi, M. R. Soltanaghaie, F. Z. Boroujeni, “Distributed Denial of Service Attacks Detection in Software Defined Networks,” Jourrnal of  Electronical & Cyber Defence, vol. 9, no. 1, pp. 43-59, 2021. (In Persian)
[2] K. Shoshian, A. Mirghadri, “Modeling of Obfuscated Multi- Stage cyber Attacks,” Jourrnal of Electronical & Cyber Defence, vol. 8, no. 2, pp. 61-73, 2020. (In Persian)
[3] M. A. Abam, M. de Berg, M. Farshi, and J. Gudmundsson, “Region-fault tolerant geometric spanners,” Discrete. Comput. Geom., vol. 41, no. 4, pp. 556-582, 2009.
[4] S. Arya, D. M. Mount, and M. Smid, “Randomized and deterministic algorithms for geometric spanners of small diameter,” 35th Annual Symposium on Foundations of Computer Science, 1994.
[5] P. B. Callahan and S. R. Kosaraju, “Faster algorithms for some geometric graph problems in higher dimensions,” fourth annual ACM-SIAM Symposium on Discrete Algorithms, 1993.
[6] P. B. Callahan and S. R. Kosaraju, “A decomposition of multidimensional point sets with applications to nearest-neighbors and body potential fields,” J. ACM., vol. 42, no. 1, pp. 67-90, 1995.
[7] D. Bakhshesh, L. Barba, P. Bose, J.-L. De Carufel, M. Damian, R. Fagerberg, M. Farshi, A. van Renssen, P. Taslakian, and S. Verdonschot, “Continuous Yao graphs,” Comp. Geom-Theor. Appl., vol. 67, pp. 42-52, 2018.
[8] D. Bakhshesh and M. Farshi, “Fault tolerancy of continuous Yao graph of angle less than ,” Inform. Process. Lett., vol. 148, pp. 13-18, 2019.
[9] P. Bose, P. Carmi, M. Farshi, A. Maheshwari, and M. H. M. Smid, “Computing the greedy spanner in near-quadratic time,” Algorithmica, vol. 58, no. 3, pp. 711-729, 2010.
[10] G. Narasimhan and M. Smid, “Geometric spanner networks”, Cambridge University, 2007.
دوره 10، شماره 4 - شماره پیاپی 40
شماره پیاپی 40، فصلنامه زمستان
بهمن 1401
صفحه 75-80
  • تاریخ دریافت: 27 بهمن 1400
  • تاریخ بازنگری: 26 مرداد 1401
  • تاریخ پذیرش: 14 شهریور 1401
  • تاریخ انتشار: 01 بهمن 1401