Skip to main content

Research Repository

Advanced Search

Radio labeling with preassigned frequencies

Bodlaender, H.L.; Broersma, H.J.; Fomin, F.V.; Pyatkin, A.V.; Woeginger, G.J.

Radio labeling with preassigned frequencies Thumbnail


Authors

H.L. Bodlaender

H.J. Broersma

F.V. Fomin

A.V. Pyatkin

G.J. Woeginger



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 preassigned operating frequency channels. This leads to the natural variants p-RL(l) and p-RL(*) of RL with l preassigned labels and an arbitrary number of preassigned 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 p-RL(*) restricted to graphs with girth at least 5. We consider the complexity of p-RL(l) and p-RL(*) for several cases in which RL is known to be polynomially solvable. On the negative side, we prove that p-RL(*) is NP-hard for cographs and for k-colorable graphs where a k-coloring is given (k at least 3). On the positive side, we derive polynomial time algorithms solving p-RL(*)} and p-RL(l) for graphs with bounded maximum degree, and for solving p-RL(l) for k-colorable graphs where a k-coloring is given.

Citation

Bodlaender, H., Broersma, H., Fomin, F., Pyatkin, A., & Woeginger, G. (2004). Radio labeling with preassigned frequencies. SIAM Journal on Optimization, 15(1), 1-16. https://doi.org/10.1137/s1052623402410181

Journal Article Type Article
Publication Date 2004-01
Deposit Date Oct 7, 2008
Publicly Available Date Oct 7, 2008
Journal SIAM Journal on Optimization
Print ISSN 1052-6234
Electronic ISSN 1095-7189
Publisher Society for Industrial and Applied Mathematics
Peer Reviewed Peer Reviewed
Volume 15
Issue 1
Pages 1-16
DOI https://doi.org/10.1137/s1052623402410181
Keywords Radio labeling, Frequency assignment, Graph algorithms, Computational complexity, Approximation algorithm, Cograph, K-coloring.
Public URL https://durham-repository.worktribe.com/output/1564107

Files

Published Journal Article (226 Kb)
PDF

Copyright Statement
©2004 Society for Industrial and Applied Mathematics




You might also like



Downloadable Citations