A new model for scheduling packet radio networks

Arunabha Sen, Mark L. Huson

Research output: Contribution to journalArticlepeer-review

75 Scopus citations


Packet radio networks are modeled as arbitrary graphs by most researchers. In this paper we show that an arbitrary graph is an inaccurate model of the radio networks. This is true because there exists a large class of graphs which will not model the radio networks. Radio networks can be modeled accurately by a restricted class of graphs called the planar point graphs. Since the radio networks can accurately be modeled only by a restricted class of graphs, the NP-completeness results for scheduling using an arbitrary graph as the model, do not correctly reflect the complexity of the problem. In this paper we study the broadcast scheduling problem using the restricted class as the model. We show that the problem remains NP-complete even in this restricted domain. We give an O(n log n) algorithm when all the transceivers are located on a line.

Original languageEnglish (US)
Pages (from-to)71-82
Number of pages12
JournalWireless Networks
Issue number1
StatePublished - 1997

ASJC Scopus subject areas

  • Information Systems
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'A new model for scheduling packet radio networks'. Together they form a unique fingerprint.

Cite this