Models and Approximation Algorithms for Channel Assignment in Radio Networks

Sven Oliver Krumke, Madhav V. Marathe, S. S. RaviWirel. Networks 2001 · OpenReview

Abstract

We consider the frequency assignment (broadcast scheduling) problem for packet radio networks. Such networks are naturally modeled by graphs with a certain geometric structure. The problem of broadcast scheduling can be cast as a variant of the vertex coloring problem (called the distance-2 coloring problem) on the graph that models a given packet radio network. We present efficient approximation algorithms for the distance-2 coloring problem for various geometric graphs including those that naturally model a large class of packet radio networks. The class of graphs considered include (r,s)-civilized graphs, planar graphs, graphs with bounded genus, etc.
BibTeX
@inproceedings{krumke2001models,
  author = {Sven Oliver Krumke and Madhav V. Marathe and S. S. Ravi},
  title = {{Models and Approximation Algorithms for Channel Assignment in Radio Networks}},
  booktitle = {Wirel. Networks},
  year = {2001},
  url = {https://openreview.net/forum?id=0wUZh1eHO7G},
}

Loading related content...

Figure