Krumke, Sven O.; Marathe, Madhav V.; Ravi, S. S. Models and approximation algorithms for channel assignment in radio networks. (English) Zbl 0996.68009 Wireless Networks 7, No. 6, 575-584 (2001). 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. Cited in 13 Documents MSC: 68M10 Network design and communication in computer systems Keywords:distance-2 coloring problem PDFBibTeX XMLCite \textit{S. O. Krumke} et al., Wirel. Netw. 7, No. 6, 575--584 (2001; Zbl 0996.68009) Full Text: DOI