ALCOMFT-TR-03-122

Hans L. Bodlaender, Hajo J. Broersma, Fedor V. Fomin, Artem V. Pyatkin and Gerhard J. Woeginer
Radio labeling with pre-assigned frequencies
Utrecht. Work package 2. December 2003.

Abstract: A radio labeling of a graph G is an assignment of pairwise distinct, positive integer labels to the vertices of G such that labels of adjacent vertices differ by at least 2. The radio labeling problem (\RL) consists in determining a radio labeling that minimizes the maximum label that is used (the so-called span of the labeling). \RL is a well-studied problem, mainly motivated by frequency assignment problems in which transmitters are not allowed to operate on the same frequency channel. We consider the special case where some of the transmitters have pre-assigned operating frequency channels. This leads to the natural variants \pRLl and \pRLx of \RL with l pre-assigned labels and an arbitrary number of pre-assigned labels, respectively.

We establish a number of combinatorial, algorithmical, and complexity-theoretical results for these variants of radio labeling. In particular, we investigate a simple upper bound on the minimum span, yielding a linear time approximation algorithm with a constant additive error bound for \pRLx restricted to graphs with girth >= 5. We consider the complexity of \pRLl and \pRLx for several cases in which \RL is known to be polynomially solvable. On the negative side, we prove that \pRLx is NP-hard for cographs and for k-colorable graphs where a k-coloring is given (k>=3). On the positive side, we derive polynomial time algorithms solving \pRLx and \pRLl for graphs with bounded maximum degree, and for solving \pRLl for k-colorable graphs where a k-coloring is given.

\medskip\noindent Keywords: Radio labeling, frequency assignment, graph algorithms, computational complexity, approximation algorithm, cograph, k-coloring.

Postscript file: ALCOMFT-TR-03-122.ps.gz (160 kb).