تعداد نشریات | 50 |
تعداد شمارهها | 2,232 |
تعداد مقالات | 20,476 |
تعداد مشاهده مقاله | 25,358,133 |
تعداد دریافت فایل اصل مقاله | 23,010,704 |
A Algorithm Pseudo Code for Approximating of Maximal Independent Set in the Unit Disc Graph | ||
Journal of New Researches in Mathematics | ||
مقاله 2، دوره 6، شماره 27، بهمن و اسفند 2020، صفحه 17-26 اصل مقاله (2.08 M) | ||
نوع مقاله: research paper | ||
نویسندگان | ||
Gholam Hassan Shirdel 1؛ Mojtaba Ghanbari 2؛ Mehdi Jalinousi3 | ||
1Associate Professor at University of Qom | ||
2Department of Mathematics, Farahan Branch, Islamic Azad University, Farahan, IRAN. | ||
3Department of Mathematics, Faculty of Science, University of Qom, Qom, IRAN. | ||
چکیده | ||
The unit disk graph is used to model a wireless sensor network when all sensors have the same communication radius. Hence, the following two optimization problems have been investigated by the researchers: maximal independent set in the network and minimal network dominating set. Since these problems are Np-hard, several algorithms have been presented for their approximation. In this paper, we have presented a honeycomb graph and algorithmic matrix methods for approximating the maximal independent set in the network. Finally, we have confirmed the validity of the algorithm and its complexity and studied it with a numerical example. Keywords: Wireless network, Independent set, Dominating set, Algorithm, Honeycomb network E. Leeuwen, Approximation Algorithms for Unit Disk Graphs, technical report, institute of information and computing sciences, utrecht university, (2004), UU-CS-2004-066. N. Bourgeois, F. Della Croce, B. Escoffier. V.Th. Paschos, Fast algorithms for min independent dominating set, Discrete Applied Mathematics 161, (2013), pp. 558-572. | ||
کلیدواژهها | ||
Keywords: Wireless network؛ Independent set؛ Dominating set؛ Algorithm؛ Honeycomb network | ||
مراجع | ||
[1] K Islam, S. Akl, H. Meijer, A constant factor distributed algorithm for computing connected dominating sets in wireless sensor networks, in: Proceedings of the 14th IEEE International Conference on Parallel and Distributed Systems (ICPADS08), December (2008), pp. 559- 566.
[2] S. Surendran, S. Vijayan, Distributed Computation of Connected Dominating Set for Multihop Wireless Networks, Procedia Computer Science 63, (2015), pp. 482-487.
[3] N. Bourgeois, F. Della Croce, B. Escoffier. V.Th. Paschos, Fast algorithms for min independent dominating set, Discrete Applied Mathematics 161, (2013), pp. 558-572.
[4] S. Kamei, H. Kakugawa, A self-stabilizing 6-approximation for the minimum connected dominating set with safe convergence in unit disk graphs, Theoretical Computer Science 428, (2012), pp. 80-90.
[5] P. M. Wightman, M.A. Labrador, A family of simple distributed minimum connected dominating set-based topology construction algorithm, Journal of Network and Computer Applications 24, (2011), pp. 1997-2010.
[6] J. Yu, L. Jia, D. Yu, G. Li, X. Cheng, Minimum connected dominating set construction in wireless networks under the beeping model, IEEE Conference on Computer Communications, (2015), pp. 972-980.
[7] S. Das, S. Barman, J. D. Sinha, Energy efficient routing in wireless sensor network, Procedia Technology 6, (2012), pp. 731-738.
[8] J.P. Mohantya, C. Mandal, C. Reade, A. Das, Construction of minimum connected dominating set in wireless sensor networks using pseudo dominating set, Ad Hoc Networks 42, (2016), pp. 61-73.
[9] M. Rai, S. r. Verma. S. Tapaswi, A power aware minimum connected dominating set for wireless sensor networks, Journal of Networks 4 (6), (2009), pp. 511-519.
[10] J. Yu, N. Wang, G. Wang, Heuristic algorithms for constructing connected dominating sets with minimum size and bounded diameter in wireless networks, in: Proceedings of Wireless Algorithms, Systems, and Applications (WASA2010), Lecture Notes in Computer Science, vol. 6221, (2010), pp. 11-20.
[11] E. Leeuwen, Approximation Algorithms for Unit Disk Graphs, technical report, institute of information and computing sciences, utrecht university, (2004), UU-CS-2004-066.
| ||
آمار تعداد مشاهده مقاله: 387 تعداد دریافت فایل اصل مقاله: 278 |