| The broadcast scheduling problem asks how an arbitrary network of broadcast transceivers operating on a shared medium may share the medium in such a way that communication over the entire network is possible. In the case where transmissions are explicitly scheduled, as opposed to be determined by contention, the problem is naturally modeled as a graph coloring problem. The canonical model is the L(1, 1)-labeling, also known as the distance-2 coloring, coloring of the graph square, or strict schedule. This coloring is, however, difficult to obtain even sub-optimally and typically uses many colors, which corresponds to an undesirable over-division of the medium.;This work introduces a relaxation of L(1, 1)-labeling called L˜(1, 1)-labeling or the pseudo-schedule. Whereas strict schedules guarantee that every path in the graph is a communication path, pseudo-schedules only require the existence of a communication path between any two vertices. The study shows that pseudo-schedules have many superior characteristics to the canonical model, provided the relaxation is acceptable. In particular, the worst case number of colors used is linear in the degree of the graph, as opposed to quadratic for strict schedules.;The formal properties of the L˜(1, 1)-labeling are comprehensively treated, including investigations of its "chromatic number," rigorous analysis of several algorithms, and proofs of hardness of optimization and approximation. Basic results on a generalization of the coloring are obtained, and nine open problems are posed for future research. |
