Home About Upload Latest Additions Statistics Contact
UT Proceedings
UT Student Theses
Dutch Academic Output Dutch Dissertations EU Publications (OpenAIRE)
Printversion
Advanced search

Radio labeling with pre-assigned frequencies

Share/Save/Bookmark

Bodlaender, H.L. and Broersma, H.J. and Fomin, F.V. and Pyatkin, A.V. and Woeginger, G.J. (2002) Radio labeling with pre-assigned frequencies. [Report]

[img]
Preview
PDF
374Kb
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 (\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.
Item Type:Report
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/65823
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page