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

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

نویسندگان

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

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

چکیده

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

کلیدواژه‌ها

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

A Greedy Algorithm for Constructing Region-Fault Tolerant Geometric Spanners

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

  • Davood Bakhshesh 1
  • Mohammad Farshi 2
1 Assistant Professor, Department of Computer Science, Bojnord University, Bojnord, Iran
2 Associate Professor, Faculty of Mathematical Sciences, Yazd University, Yazd, Iran
چکیده [English]

In this paper, we consider the problem of constructing the region-fault tolerant geometric spanners when the problem is restricted to a subclass of convex regions. Let S be a set of n points in the plane. In particular, in this paper, a greedy algorithm for constructing the region-fault tolerant geometric spanner of S where the region faults are a set of at most k half-planes with parallel boundaries is presented. We show that the proposed algorithm has the time complexity O(kn^3 log⁡n ), and the generated graph contains O(kn) edges. To the best of our knowledge, the best-known algorithm to construct the region-fault tolerant geometric spanner of S takes O(n log^2⁡n) time and the generated graph has O(n log⁡n) edges.

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

  • Geometric spanners
  • Communication networks
  • Greedy algorithm

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

هم رسانی

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

آمار