Wireless communication graphs

T. Nieberg, Johann L. Hurink

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

20 Citations (Scopus)
51 Downloads (Pure)


We consider graph models which represent communication in wireless ad-hoc networks. In such networks, each node equipped with a radio has a certain transmission range, and all surrounding nodes in this range can receive a transmission. In ideal settings, this transmission range creates a circular disk around each node, so that disk intersection graphs are common models. We review some properties of these disk graphs and introduce more realistic and sophisticated geometric graphs to model wireless communication. These models are explored and exploited to obtain approximability results for two important problems, maximum independent sets and minimum dominating sets. Although these more realistic models have less structure, the same complexity status as for disk graphs can be achieved. Furthermore, we present simple, constant factor approximation algorithms for the problems that run locally in each node, and that do not rely on positional information, making them independent of localization.
Original languageEnglish
Title of host publicationISSNIP 2004
Subtitle of host publicationproceedings of the 2004 Intelligent Sensors, Sensor Networks & Information Processing Conference
EditorsM Palaniswami, B. Krishnamachari, A. Sowmya, S. Challa
Place of PublicationPiscataway, NJ
Number of pages6
ISBN (Print)0-7803-8894-1
Publication statusPublished - Dec 2004
Event1st International Conference on Intelligent Sensors, Sensor Networks and Information Processing, ISSNIP 2004 - Melbourne, Australia
Duration: 14 Dec 200417 Dec 2004
Conference number: 1

Publication series



Conference1st International Conference on Intelligent Sensors, Sensor Networks and Information Processing, ISSNIP 2004
Abbreviated titleISSNIP


  • METIS-220430
  • EC Grant Agreement nr.: FP5/34734
  • EWI-7657
  • IR-48713


Dive into the research topics of 'Wireless communication graphs'. Together they form a unique fingerprint.

Cite this