آمار
| تعداد نشریات | 36 |
| تعداد شماره‌ها | 1,192 |
| تعداد مقالات | 8,579 |
| تعداد مشاهده مقاله | 6,988,734 |
| تعداد دریافت فایل اصل مقاله | 4,032,598 |
یک الگوریتم حریصانه برای ساخت پوشاننده هندسی تحمل‌پذیر ناحیه-خطا | ||
| پدافند الکترونیکی و سایبری | ||
| مقاله 8، دوره 10، شماره 4 - شماره پیاپی 40، بهمن 1401، صفحه 75-80 اصل مقاله (836.64 K) | ||
| نوع مقاله: مقاله پژوهشی | ||
| نویسندگان | ||
| داود بخشش* 1؛ محمد فرشی2 | ||
| 1استادیار، گروه علوم کامپیوتر، دانشگاه بجنورد، بجنورد، ایران | ||
| 2دانشیار، دانشکده علوم ریاضی، دانشگاه یزد، یزد، ایران | ||
| تاریخ دریافت: 27 بهمن 1400، تاریخ بازنگری: 26 مرداد 1401، تاریخ پذیرش: 14 شهریور 1401 | ||
| چکیده | ||
| در این مقاله، مسئله ساخت پوشاننده هندسی تحمل‌پذیر ناحیه-خطا مقید به زیر کلاسی از نواحی محدب، مورد بحث قرار می‌گیرد. فرض کنید که S مجموعه‌ای از n نقطه در صفحه باشد. به طور دقیق‌تر، در این مقاله، یک الگوریتم حریصانه برای ساخت پوشاننده هندسی تحمل-پذیر ناحیه-خطا در حالتی که ناحیه‌های خطا، مجموعه ای از نیم صفحه ها با مرز موازی با حداکثر k خط است، بررسی می‌شود. نشان داده می‌شود که پیچیدگی زمانی الگوریتم پیشنهادی O(kn^3 logn) و گراف تولید شده توسط آن دارای O(kn) یال است. طبق آخرین اطلاعاتی که داریم بهترین الگوریتمی که برای ساخت یک پوشاننده هندسی تحمل‌پذیر ناحیه-خطا برای مجموعه نقطه S ارائه شده است، دارای زمان اجرای O(n log^2n) است و گراف تولید شده توسط آن دارای O(n logn) یال است. | ||
| کلیدواژه‌ها | ||
| پوشاننده هندسی؛ شبکه‌های ارتباطی؛ الگوریتم حریصانه | ||
| عنوان مقاله [English] | ||
| A Greedy Algorithm for Constructing Region-Fault Tolerant Geometric Spanners | ||
| نویسندگان [English] | ||
| Davood Bakhshesh1؛ Mohammad Farshi2 | ||
| 1Assistant Professor, Department of Computer Science, Bojnord University, Bojnord, Iran | ||
| 2Associate 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 logn ), 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^2n) time and the generated graph has O(n logn) edges. | ||
| کلیدواژه‌ها [English] | ||
| Geometric spanners, Communication networks, Greedy algorithm | ||
| مراجع | ||
|
[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. | ||
|
آمار تعداد مشاهده مقاله: 96 تعداد دریافت فایل اصل مقاله: 104 |
||