June 10, 2023
Doost Ali Mojdeh

Doost Ali Mojdeh

Degree: Professor
Address: Department of Mathematics, University of Mazandaran, Babolsar, Iran
Education: Ph.D in Mathematics (Graph Theory and Combinatorics)
Phone: 011-35302448
Faculty: Faculty of Mathematical Sciences


Title A New Approximation Algorithm for Maximal Independent Set in Wireless Sensor Networks
Type Article
Wireless network, independent set, dominating set, algorithm.
Journal IJCSNS International Journal of Computer Science and Network Security
Researchers Mojtaba Ghanbari (First researcher) , Doost Ali Mojdeh (Second researcher) , Mehdi Ramezani (Third researcher)


The unit disk graph is a mathematical model for wireless sensor networks when all sensors have the same communication radius. There are two classical optimization problems on graphs, relevant to unit disk graph, models of mobile ad hoc networks, maximal independent set of nodes, that is also a dominating set, and minimum connected dominating set. We propose decomposition of connected unit disk graph into 1- by-1 boxes and two new matrices corresponding to this graph (Packing matrix and Independent vertex matrix) for approximating maximal independent set. If the graph is bounded, then the considered problems can be solved in polynomial time. We prove this fact indirectly by presenting dynamic programming algorithm and show that these results are optimal