Radio labeling with pre-assigned frequencies

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

Research output: Book/ReportReportOther research output

3 Citations (Scopus)
85 Downloads (Pure)


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 (\mbox{\sc RL}) consists in determining a radio labeling that minimizes the maximum label that is used (the so-called span of the labeling). \mbox{\sc 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 \mbox{\sc p-RL($l$)} and \mbox{\sc p-RL($*$)} of \mbox{\sc RL} with $l$ pre-assigned labels and an arbitrary number of pre-assigned labels, respectively.
Original languageEnglish
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Publication statusPublished - 2002

Publication series

PublisherDepartment of Applied Mathematics, University of Twente
ISSN (Print)0169-2690


  • MSC-94C15
  • MSC-05C78
  • MSC-05C15
  • IR-65823
  • MSC-68W25
  • EWI-3456
  • MSC-68R10


Dive into the research topics of 'Radio labeling with pre-assigned frequencies'. Together they form a unique fingerprint.

Cite this