Doost Ali Mojdeh

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