2024 : 3 : 29
Doost Ali Mojdeh

Doost Ali Mojdeh

Academic rank: Professor
ORCID:
Education: PhD.
ScopusId:
Faculty: Faculty of Mathematical Sciences
Address: Department of Mathematics, University of Mazandaran, Babolsar, Iran
Phone: 011-35302448

Research

Title
A New Approximation Algorithm for Maximal Independent Set in Wireless Sensor Networks
Type
JournalPaper
Keywords
Wireless network, independent set, dominating set, algorithm.
Year
2017
Journal IJCSNS International Journal of Computer Science and Network Security
DOI
Researchers Mojtaba Ghanbari ، Doost Ali Mojdeh ، Mehdi Ramezani

Abstract

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