roadcast Scheduling in Packet Radio Networks
Dung T. Huynh · 1998
There are several graph theoretic models of packet radio networks. Hoir3evel; an NP-completeness result for a more general model does not necessarilj implj the same result for a more restricted model. In this papel; bve show that the problem ofjinding 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 Erd6s’ algorithm for computing maxinial 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 efJicient distributed implementation.