Bounds for the frequency assignment problem

DOI10.1016/S0012-365X(96)00257-9MaRDI QIDQ1356496zbMATH OpenOpenAlexFDO

Authors O. Diekmann, Derek H. Smith, Steve Hurley

Publication date 8 October 1997

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(96)00257-9

bounds frequency assignment T-colouring transmitter

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Applications of graph theory (05C90)

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.

Cites work

Cited in

(37)

This page was built for publication: Bounds for the frequency assignment problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1356496)