Models and approximation algorithms for channel assignment in radio networks

We consider the frequency assignment (broadcast scheduling) problem for pac ket radio networks. Such networks are naturally modeled by graphs with a ce rtain 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 clas s of packet radio networks. The class of graphs considered include (r, s)-c ivilized graphs, planar graphs, graphs with bounded genus, etc.