×

Models and approximation algorithms for channel assignment in radio networks. (English) Zbl 0996.68009

Summary: 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.

MSC:

68M10 Network design and communication in computer systems
PDFBibTeX XMLCite
Full Text: DOI