Bounds for the frequency assignment problem
type: Item
instance of: scholarly article
title: Bounds for the frequency assignment problem
zbMATH Open document ID: 0873.05041
DOI: 10.1016/S0012-365X(96)00257-9
author: O. Diekmann
published in: Discrete Mathematics
publication date: 1997-10-08T00:00:00Z
review text: The problem of assigning radio frequencies to a set of transmitters is related to the theory of vertex colourings of graphs. Let \(F=\{0,1,\ldots,K\}\) be the set of available frequencies and \(\{0\} \subseteq T_0 \subseteq T_1 \subseteq \cdots \subseteq T_L \subseteq F\). The constraint graph has one vertex for each transmitter and edges with labels in \(\{0,1,\ldots,L\}\) describing interference. A frequency assignment in a constraint graph \(G=(V,E)\) is a mapping \(f : V \to F\) such that \(|f(x)-f(y)|\notin T_i\) if edge \(\{x,y\}\) has label \(i\). For a given constraint graph \(G\) with edge labels and sets \(T_i\) the minimum value of \(K\) such that a frequency assignment exists is called the span of \(G\). For a large number of transmitters heuristic methods are used to find assignments with small \(K\). This paper proves lower bounds for the span and describes methods to reduce the size of the problem.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C90
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1018543
zbMATH Keywords: T-colouring
zbMATH Keywords: frequency assignment
zbMATH Keywords: transmitter
zbMATH Keywords: bounds
MaRDI profile type: Publication
cites work: Q3035310
cites work: A tabu search algorithm for frequency assignment
cites work: On the use of some known methods for \(T\)-colorings of graphs
cites work: Q3322121
cites work: Q3340907
cites work: Solving the maximum clique problem using a tabu search approach
cites work: On the shortest spanning subtree of a graph and the traveling salesman problem
cites work: Q4336207
cites work: Sur le coloriage des graphs
cites work: \(T\)-colorings of graphs: recent results and open problems
cites work: Q3798679
full work available at URL: s0012-365x(96)00257-9
OpenAlex ID: W2111716442
description: scientific article; zbMATH DE number 1018543