Channel assignment for digital networks: a bound and an algorithm


Jeannette Janssen
Mark MacIsaac
Kyle Schmeisser

Author Addresses: 

Jeannette Janssen (
Mark MacIsaac (
Kyle Schmeisser (
Dept. of Mathematics and Statistics
Dalhousie University
B3H 3J5 Halifax, NS


The problem of channel assignment in digital networks can be formulated as follows. Services to be broadcast at a transmitter must be packed into blocks, and each block must be assigned a frequency channel. This assignment must satisfy bandwidth and interference constraints. The objective is to minimize spectrum use.

Mathematically, the problem corresponds to a generalized graph colouring problem with a flavour of bin packing. In this paper, we give a new lower bound on spectrum use for this problem, derived from intersecting cliques. We also give a near-optimal, efficient algorithm to assign frequency channels to blocks for the case where the interference graph is a cycle.

Tech Report Number: 
Report Date: 
May 1, 2002
PDF icon CS-2002-03.pdf247.14 KB