Approximation algorithms for the freeze tag problem inside polygons

Rajabi-Alni, Fatemeh; Minaei-Bidgoli, Behrouz; Bagheri, Alireza

doi:10.22108/toc.2025.143753.2229

تعداد نشریات	43
تعداد شماره‌ها	1,830
تعداد مقالات	14,887
تعداد مشاهده مقاله	40,829,893
تعداد دریافت فایل اصل مقاله	15,840,835

	Approximation algorithms for the freeze tag problem inside polygons
Transactions on Combinatorics
دوره 15، شماره 2، شهریور 2026، صفحه 137-145 اصل مقاله (817.62 K)
نوع مقاله: Research Paper
شناسه دیجیتال (DOI): 10.22108/toc.2025.143753.2229
نویسندگان
Fatemeh Rajabi-Alni^* ¹؛ Behrouz Minaei-Bidgoli¹؛ Alireza Bagheri²
¹Department of Computer Engineering, Iran University of Science and Technology, Tehran, Iran
²Computer Engineering Department, Amirkabir University of Technology (Tehran Polytechnic), Tehran, Iran
چکیده
The freeze tag problem (FTP) aims to awaken a swarm of robots with one or more initially awake robots as soon as possible. Each awake robot must touch a sleeping robot to wake it up. Once a robot is awakened, it can assist in awakening other sleeping robots. We study this problem inside a polygonal domain and present approximation algorithms for it.
کلیدواژه‌ها
Freeze tag problem؛ swarm robotics؛ polygonal domain؛ $t$-spanner؛ geodesic graphs

مراجع
[1] Y. Z. A. Lubiw, The visibility freeze-tag problem, 24th annual fall workshop on computational geometry (FWCG), University of Connecticut, (2014). [2] M. A. Abam, Spanners for geodesic graphs and visibility graphs, Algorithmica 80 no. 2 (2018) 515–529. [3] Z. Abel, H. A. Akitaya and J. Yu, Freeze tag awakening in 2D is NP-hard, 27th 24th annual fall workshop on computational geometry (FWCG), Stony Brook University, Stony Brook, (2017). [4] A. Ahadi and A. Zarei, Connecting guards with minimum steiner points inside simple polygons, Theoret. Comput. Sci., 775 (2019) 26–31. [5] N. Ahuja, H. Bikkavilli, Z. Chen, M. M. Eshaghian-Wilner, A. Mittal, K. Ravicz, B. Sangal, S. Sarma, M. Schlesinger and A. Wilner, Real-time cellular-level imaging and medical treatment with a swarm of wireless multifunctional robots, J. Supercomput., 78 no. 1 (2022) 1923–1943. [6] D. Albiero, A. P. Garcia, C. K. Umezu and R. L. de Paulo, Swarm robots in mechanized agricultural operations: A review about challenges for research, Comput. Electron. Agric., 193 (2022) p. 106608. [7] E. Arkin, M. Bender, S. Fekete, J. Mitchell and M. Skutella, The freeze-tag problem: how to wake up a swarm of robots, Algorithmica, 46 no. 2 193–221. [8] P. Bose, P. Morin, A. van Renssen and S. Verdonschot, The θ5 -graph is a spanner, Comput. Geom., 48 no. 2 (2015) 108–119. [9] M. Gan, Q. Qian, D. Li, Y. Ai and X. Liu, Capturing the swarm intelligence in truckers: The foundation analysis for future swarm robotics in road freight, Swarm Evol. Comput., 62 (2021) p. 100845. [10] P. A. Hoeher, J. Sticklus and A. Harlakin, Underwater optical wireless communications in swarm robotics: A tutorial, IEEE. Commun. Surv. Tutorials, 23 no. 4 (2021) 2630–2659. [11] M. P. Johnson, Easier hardness for 3D freeze-tag, 27th annual fall workshop on computational geometry (FWCG), Stony Brook University, Stony Brook, (2017). [12] Z. Moezkarimi and A. Bagheri, A PTAS for geometric 2-FTP, Inform. Process. Lett., 114 no. 12 (2014) 670–675. [13] E. Osaba, J. Del Ser, A. Iglesias and X.-S. Yang, Soft computing for swarm robotics: New trends and applications, J. Comput. Sci., 39 (2020) p. 101049. [14] M. Senanayake, I. Senthooran, J. C. Barca, H. Chung, J. Kamruzzaman and M. Murshed, Search and tracking algorithms for swarms of robots: A survey, Rob. Auton. Syst., 75 (2016) 422–434. [15] M. O. Sztainberg, E. Arkin, M. Bender and J. Mitchell, Analysis of heuristics for the freeze-tag problem, Algorithm Theory–SWAT 2002, Lecture Notes in Comput. Sci., 2368, Springer, Berlin, 2002. [16] Q. Tang, Z. Xu, F. Yu, Z. Zhang and J. Zhang, Dynamic target searching and tracking with swarm robots based on stigmergy mechanism, Rob. Auton. Syst., 120 (2019) p. 103251. [17] A. van Renssen and G. Wong, Bounded-degree spanners in the presence of polygonal obstacle, Theor. Comput. Sci., 854 (2021) 159–173.
آمار تعداد مشاهده مقاله: 308 تعداد دریافت فایل اصل مقاله: 99

سامانه مدیریت نشریات علمی. طراحی و پیاده سازی از سیناوب

پیوندهای مفید

اخبار و اعلانات

آمار

Approximation algorithms for the freeze tag problem inside polygons