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)
28 Downloads (Pure)

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.
Original languageEnglish
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Publication statusPublished - 2002

Publication series

NameMemorandum
PublisherDepartment of Applied Mathematics, University of Twente
No.1636
ISSN (Print)0169-2690

Fingerprint

Labeling
Transmitter
Frequency Assignment
Assignment Problem
Pairwise
Assignment
Adjacent
Distinct
Minimise
Integer
Arbitrary
Graph in graph theory

Keywords

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

Cite this

Bodlaender, H. L., Broersma, H. J., Fomin, F. V., Pyatkin, A. V., & Woeginger, G. J. (2002). Radio labeling with pre-assigned frequencies. (Memorandum; No. 1636). Enschede: University of Twente, Department of Applied Mathematics.
Bodlaender, H.L. ; Broersma, H.J. ; Fomin, F.V. ; Pyatkin, A.V. ; Woeginger, G.J. / Radio labeling with pre-assigned frequencies. Enschede : University of Twente, Department of Applied Mathematics, 2002. (Memorandum; 1636).
@book{390f4d2d246747a7b036f89bd50bb9bd,
title = "Radio labeling with pre-assigned frequencies",
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.",
keywords = "MSC-94C15, MSC-05C78, MSC-05C15, IR-65823, MSC-68W25, EWI-3456, MSC-68R10",
author = "H.L. Bodlaender and H.J. Broersma and F.V. Fomin and A.V. Pyatkin and G.J. Woeginger",
year = "2002",
language = "English",
series = "Memorandum",
publisher = "University of Twente, Department of Applied Mathematics",
number = "1636",

}

Bodlaender, HL, Broersma, HJ, Fomin, FV, Pyatkin, AV & Woeginger, GJ 2002, Radio labeling with pre-assigned frequencies. Memorandum, no. 1636, University of Twente, Department of Applied Mathematics, Enschede.

Radio labeling with pre-assigned frequencies. / Bodlaender, H.L.; Broersma, H.J.; Fomin, F.V.; Pyatkin, A.V.; Woeginger, G.J.

Enschede : University of Twente, Department of Applied Mathematics, 2002. (Memorandum; No. 1636).

Research output: Book/ReportReportOther research output

TY - BOOK

T1 - Radio labeling with pre-assigned frequencies

AU - Bodlaender, H.L.

AU - Broersma, H.J.

AU - Fomin, F.V.

AU - Pyatkin, A.V.

AU - Woeginger, G.J.

PY - 2002

Y1 - 2002

N2 - 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.

AB - 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.

KW - MSC-94C15

KW - MSC-05C78

KW - MSC-05C15

KW - IR-65823

KW - MSC-68W25

KW - EWI-3456

KW - MSC-68R10

M3 - Report

T3 - Memorandum

BT - Radio labeling with pre-assigned frequencies

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -

Bodlaender HL, Broersma HJ, Fomin FV, Pyatkin AV, Woeginger GJ. Radio labeling with pre-assigned frequencies. Enschede: University of Twente, Department of Applied Mathematics, 2002. (Memorandum; 1636).