A complementary slackness based method for finding minimum number of servers in wireless networks

In this paper, we model servers of a wireless network as a dominating set and show that the problem of finding minimum dominating set in functigraphs is NP-complete. Then we model the problem of finding minimum dominating set in functigraphs as an integer linear programming problem, and we provide a complementary slackness based algorithm for finding dominating sets in functigraphs and we will show that this algorithm achieves an approximation factor of  1.

کلیدواژه ها:

Wireless networks ، dominating sets ، integer programming ، LP-relaxation ، NP-complete