Broadcast scheduling in packet radio networks

There are several graph theoretic models of packet radio networks. However, an NP-completeness result for a more general model does not necessarily imply the same result for a more restricted model. In this paper we show that the problem of finding a maximum set of broadcasting stations is NP-complete for unit disc graphs which are perhaps the simplest model of packet radio networks. We propose a new heuristic based on Erdos´ algorithm for computing maximal independent sets in undirected graphs. We do some experiments to show that the proposed heuristic performs consistently better than other methods. We also discuss an efficient distributed implementation