Radio Labeling with Pre-assigned Frequencies

Hans L. Bodlaender, Haitze J. Broersma, Fedor V. Fomin, Artem Pyatkin, Gerhard Woeginger

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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 pre-assigned labels and an arbitrary number of pre-assigned labels, respectively.

We establish a number of combinatorial, algorithmical, and complexitytheoretical 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 ≥ 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 ≥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.
Original languageEnglish
Title of host publicationAlgorithms — ESA 2002
Subtitle of host publication10th Annual European Symposium Rome, Italy, September 17–21, 2002 Proceedings
EditorsRalf Möhring, Rajeev Raman
Place of PublicationBerlin
PublisherSpringer
Pages211-222
ISBN (Electronic)978-3-540-45749-7
ISBN (Print)978-3-540-44180-9
DOIs
Publication statusPublished - 2002
Event10th Annual European Symposium on Algorithms, ESA 2002 - Rome, Italy
Duration: 17 Sep 200221 Sep 2002
Conference number: 10

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume2461
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference10th Annual European Symposium on Algorithms, ESA 2002
Abbreviated titleESA
CountryItaly
CityRome
Period17/09/0221/09/02

Fingerprint

Labeling
Graph in graph theory
Transmitter
Colouring
Frequency Assignment
Cographs
Girth
Linear-time Algorithm
Assignment Problem
Maximum Degree
Polynomial-time Algorithm
Error Bounds
Approximation Algorithms
Pairwise
Assignment
Adjacent
NP-complete problem

Keywords

  • METIS-208179

Cite this

Bodlaender, H. L., Broersma, H. J., Fomin, F. V., Pyatkin, A., & Woeginger, G. (2002). Radio Labeling with Pre-assigned Frequencies. In R. Möhring, & R. Raman (Eds.), Algorithms — ESA 2002: 10th Annual European Symposium Rome, Italy, September 17–21, 2002 Proceedings (pp. 211-222). (Lecture Notes in Computer Science; Vol. 2461). Berlin: Springer. https://doi.org/10.1007/3-540-45749-6_22
Bodlaender, Hans L. ; Broersma, Haitze J. ; Fomin, Fedor V. ; Pyatkin, Artem ; Woeginger, Gerhard. / Radio Labeling with Pre-assigned Frequencies. Algorithms — ESA 2002: 10th Annual European Symposium Rome, Italy, September 17–21, 2002 Proceedings. editor / Ralf Möhring ; Rajeev Raman. Berlin : Springer, 2002. pp. 211-222 (Lecture Notes in Computer Science).
@inproceedings{fd810bfcf9064770bdca4a2ec92c3d04,
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 (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 pre-assigned labels and an arbitrary number of pre-assigned labels, respectively.We establish a number of combinatorial, algorithmical, and complexitytheoretical 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 ≥ 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 ≥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.",
keywords = "METIS-208179",
author = "Bodlaender, {Hans L.} and Broersma, {Haitze J.} and Fomin, {Fedor V.} and Artem Pyatkin and Gerhard Woeginger",
year = "2002",
doi = "10.1007/3-540-45749-6_22",
language = "English",
isbn = "978-3-540-44180-9",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "211--222",
editor = "Ralf M{\"o}hring and Rajeev Raman",
booktitle = "Algorithms — ESA 2002",

}

Bodlaender, HL, Broersma, HJ, Fomin, FV, Pyatkin, A & Woeginger, G 2002, Radio Labeling with Pre-assigned Frequencies. in R Möhring & R Raman (eds), Algorithms — ESA 2002: 10th Annual European Symposium Rome, Italy, September 17–21, 2002 Proceedings. Lecture Notes in Computer Science, vol. 2461, Springer, Berlin, pp. 211-222, 10th Annual European Symposium on Algorithms, ESA 2002, Rome, Italy, 17/09/02. https://doi.org/10.1007/3-540-45749-6_22

Radio Labeling with Pre-assigned Frequencies. / Bodlaender, Hans L.; Broersma, Haitze J.; Fomin, Fedor V.; Pyatkin, Artem; Woeginger, Gerhard.

Algorithms — ESA 2002: 10th Annual European Symposium Rome, Italy, September 17–21, 2002 Proceedings. ed. / Ralf Möhring; Rajeev Raman. Berlin : Springer, 2002. p. 211-222 (Lecture Notes in Computer Science; Vol. 2461).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Radio Labeling with Pre-assigned Frequencies

AU - Bodlaender, Hans L.

AU - Broersma, Haitze J.

AU - Fomin, Fedor V.

AU - Pyatkin, Artem

AU - Woeginger, Gerhard

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 (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 pre-assigned labels and an arbitrary number of pre-assigned labels, respectively.We establish a number of combinatorial, algorithmical, and complexitytheoretical 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 ≥ 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 ≥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.

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 (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 pre-assigned labels and an arbitrary number of pre-assigned labels, respectively.We establish a number of combinatorial, algorithmical, and complexitytheoretical 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 ≥ 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 ≥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.

KW - METIS-208179

U2 - 10.1007/3-540-45749-6_22

DO - 10.1007/3-540-45749-6_22

M3 - Conference contribution

SN - 978-3-540-44180-9

T3 - Lecture Notes in Computer Science

SP - 211

EP - 222

BT - Algorithms — ESA 2002

A2 - Möhring, Ralf

A2 - Raman, Rajeev

PB - Springer

CY - Berlin

ER -

Bodlaender HL, Broersma HJ, Fomin FV, Pyatkin A, Woeginger G. Radio Labeling with Pre-assigned Frequencies. In Möhring R, Raman R, editors, Algorithms — ESA 2002: 10th Annual European Symposium Rome, Italy, September 17–21, 2002 Proceedings. Berlin: Springer. 2002. p. 211-222. (Lecture Notes in Computer Science). https://doi.org/10.1007/3-540-45749-6_22