CHAPTER 5
Channel Assignment and Graph Labeling
JEANNETTE C. M. JANSSEN
Department of Mathematics and Statistics, Dalhousie University, Halifax, N.S., Canada
5.1 INTRODUCTION
Due to rapid growth in the use of wireless communication services and the corresponding
scarcity and high cost of radio spectrum bandwidth, it has become increasingly important
for cellular network operators to maximize spectrum efficiency. Such efficiency can be
achieved by optimal frequency reuse, i.e., the simultaneous use of the same part of the ra-
dio spectrum by communication links in different locations of the network. Optimal fre-
quency reuse is constrained by noise levels, resulting from interference between commu-
nication links, that must be kept at acceptable levels (see [25]).
In the previous chapter [28], the problem of assigning channels to minimize spectrum
use while satisfying interference constraints was discussed in its simplest form. In this
form, each pair of cells in the network can either use the same channel simultaneously or
not. However, for networks based on frequency division (FDMA) or time division
(TDMA), there can be a significant difference in the amount of interference between
channels that are near each other in the radio spectrum and channels that are far apart.
This implies that the distance between cells that use channels close together in frequency
must be greater than the distance between cells that use channels that are far apart. The
constraints for channel assignment resulting from this consideration are referred to as
channel separation constraints.
As discussed in [28], a graph model can be used for the channel assignment problem.
The nodes of the graph correspond to cells or their base stations and the edges represent
cell adjacency. We assume that a fixed demand for channels is given for each cell, and that
a channel assignment assigning exactly that many channels to the cell must be found. The
algorithms reviewed here apply to the static situation. However, in many cases the same
algorithms can also be used in the dynamic situation, where the demand for channels
changes over time. Algorithms based on a preassigned set of channels per node (such as
Algorithms A and AЈ, described in Section 5.3) can be directly adapted to the dynamic
case. Other algorithms can be adapted if limited reassignment of the channels used to car-

i
.
The constraint c
0
represents the separation between channels assigned to the same cell
and is referred to as the cosite constraint. The constraints between different cells are re-
ferred to as intersite constraints. Although the cosite constraint is often high compared to
the other constraints, the intersite constraints most often take smaller values, especially
one and two. In somewhat confusing terms, an intersite constraint of one, which indicates
that channels assigned to the corresponding cells must be distinct, is often referred to as a
cochannel constraint. An intersite constraint of two, which codifies the requirement that
channels assigned to a pair of cells cannot be next to each other in the radio spectrum, is
often called an adjacent-channel constraint. Note further that graph labeling usually refers
to an assignment of one channel per node, so that c
0
is irrelevant. In Section 5.3, we will
show how graph labelings can be useful in finding algorithms for channel assignment
problems with demands greater than 1. We will now proceed with a formal definition of
the model described, and a review of other relevant models.
5.1.1 Graph Models
The definitions and notations used in this chapter are consistent with those introduced in
the previous chapter [28]. For a general background on graph theory, the reader is referred
to [8].
A constrained graph G = (V, E, c
0
, ..., c
k
) is a graph G = (V, E) and positive integer
parameters c
0

96
CHANNEL ASSIGNMENT AND GRAPH LABELING
c
0
, ..., c
k
) is an assignment f of sets of nonnegative integers (representing the channels)
to the nodes of G satisfying the conditions:
| f (u)| = w(u) for all u
ʦ
V
i
ʦ
f (u) and j
ʦ
f (v) ⇒ |i – j| Ն c
ᐉ
for all u, v ʦ V so that d
G
(u, v) = ᐉ.
The bandwidth used by a channel assignment is represented by its span. The span S( f )
of a channel assignment f of a constrained weighted graph is the difference between the
lowest and the highest channel assigned by f. The span of a constrained, weighted graph
(G, w) denoted by S(G, w), is the minimum span of any channel assignment for (G, w).
The regular layouts often used for cellular networks can be modeled as subgraphs of an
infinite lattice. An n-dimensional lattice is a collection of points in ޒ
n
by n that are linear
integer combinations of the generating vectors e
1

k
if for all pairs of nodes u, v at distance d = d
G
(u, v) Յ k from each other, |f(u) –
f(v)| Ն c
d
. The span S( f ) of a labeling f is defined as S( f ) = max f (V), the value of the
highest label assigned by f. Note: if the lowest label used is zero, then the definition of the
span of a graph labeling is consistent with that of a channel assignment.
In order to use a graph labeling to find channel assignments for weight vectors with
components greater than 1, one must know the “offset” that is needed when the labeling is
repeated. This notion is captured in the definition of cyclic span. The cyclic span of a la-
beling f is the smallest number M such that, for all pairs of nodes u, v at graph distance d
from each other (d
Յ
k), |f(u) – f(v)| Ն M – c
d
.
The first paper to consider graph labelings for constraints c
1
, ... c
k
, [15], referred to
them as L(c
1
, ... c
k
)-labelings. The specific case of a graph labeling with c
1
= 2, c

0
, d
1
, ..., d
k
is given and a channel assignment f has to fulfill the
condition that for any pair of nodes (cells) u and v
i
ʦ
f (u) and j
ʦ
f (v) and |i – j| = ᐉ ⇒ d(u, v) > d
ᐉ
The distance d(u, v) can either be used to mean the physical distance between the cor-
responding base stations or the graph distance between the nodes. If graph distance is
used, then the correspondence between this model and our model is that d
ᐉ
= min{i|c
i
< ᐉ}
for ᐉ > 0, d
0
= k + 1, and c
i
= min{ᐉ|i > d
ᐉ
}. In this model, d
0
equals the reuse distance.
Another model assumes that for each pair of adjacent nodes u, v a separation constraint

sults without theoretical analysis. The second group focuses on implementation issues
arising from specific technologies and protocols, and the final group gives exact solutions
to certain specific instances by using combinatorial optimization methods such as integer
programming.
The term “performance ratio” refers here to the asymptotic performance ratio. Hence, a
channel assignment f is said to be optimal for a weighted constrained graph G if S( f ) =
S(G, w) + O(1). The span is assumed to be a function of the weights and the size of the
graph, so the O(1) term can include terms dependent on the constraints c
0
, c
1
, ..., c
k
. An
approximation algorithm for channel assignment has performance ratio k when the span
of the assignment produced by the algorithm on (G, w) is at most kS(G, w)+ O(1).
The version of the channel assignment problem considered here is a generalization of
98
CHANNEL ASSIGNMENT AND GRAPH LABELING
the graph coloring problem, which is well known to be NP-complete for general graphs. A
reduction to Hamiltonian paths shows that channel assignment is NP-complete even for
graphs of diameter 2 with constraints c
1
= 2, c
2
= 1. This was proved in the seminal paper
on graph labelings by Griggs and Yeh [15]. (The same result, with the same proof, was
presented without reference to the original result six years later by Fotakis and Spirakis in
[11].)
McDiarmid and Reed [27] have proved that multicoloring is NP-hard for hexagon

resentations of the channel assignment problem as a graph coloring problem or a traveling
salesman problem. In this section, I will give an overview of the lower bounds available
for channel assignment with constraints.
An early paper by Gamst [12] presents a number of lower bounds based on sets of
nodes that have a prescribed minimum constraint between them. More precisely, a d-
clique in a constrained graph G = (V, E, c
0
, c
1
, . . .) is a set of nodes so that for any pair
of nodes u, v, d
G
(u, v) Յ d. Note that a d-clique corresponds to a clique in G
d
, the graph
obtained from G by adding edges between all pairs of nodes with distance at most d in
G.
Any two nodes in a d-clique have constraint at least c
d
between them, and thus any two
channels assigned to nodes in the d-clique have to have separation at least c
d
. This leads
5.2 LOWER BOUNDS
99
directly to the following bound, adapted from [12]. For any constrained, weighted graph
(G, w), where G = (V, E, c
0
, c
1

k + 1, ..., k + c
d
– 1}. This leads to the following bound, stated slightly differently in
[33]:
S(G, w) Ն max{c
d
w(H)/
␣
d
(H) – c
d
|H a subgraph of G} (5.3)
5.2.1 Traveling Salesman Bounds
Several authors ([22, 15, 17, 31, 33]) have noted that the channel assignment problem
can be reframed as a generalization of the traveling salesman problem (TSP). For any
channel assignment of a graph with weight one on every node, an enumeration of the
nodes in nondecreasing order of the assigned channels will constitute an open TSP tour
(Hamiltonian path) of the nodes. The difference between the channels assigned to two
consecutive nodes in the tour is at least equal to the constraint between the nodes.
Hence, the span of the assignment is at least equal to the cost of the tour, with the cost
of traveling between two nodes u and v being the constraint between these two nodes.
Therefore, the cost of an optimal TSP tour is a lower bound on the span of the channel
assignment.
If the weights are greater than one, one can derive a similar bound from a generalized
TSP problem. Here, the goal is to find a minimum cost tour such that every node v is vis-
ited w(v) times. Note that this corresponds to a regular TSP if every node v is expanded
into a clique of size w(v), where the cost between any two nodes in this clique is defined
to be c
0
, whereas the nodes in cliques corresponding to different nodes of the original

be the vector that represents the constraints between pairs of nodes of G. Given a set
of nodes V, a weight vector w ʦ ޚ
V
and a cost vector c ʦ ޚ
+
V×V
, let TSP(V, w, c) be the
100
CHANNEL ASSIGNMENT AND GRAPH LABELING
cost of the minimum traveling salesman tour through V, where each node v is visited w(v)
times, and costs are given by c. Then the following bound, first given in [33], holds:
S(G, w) Ն max{TSP(U, w, c
G
) – c
0
|U
ʕ
V
G
} (5.4)
(Vectors w and c
G
are considered to be restricted to U.)
The minimal TSP tour can be as hard to compute as the optimal channel assignment, so
this bound is only of practical interest for relatively small channel assignment problems.
However, the TSP approach can be used to find a lower bound that is easy to calculate. As
mentioned in [33], the lower bound for the TSP given by Christofides (see for example
[7]), which is derived from minimum spanning trees and is easy to compute, may be used
to approximate the TSP bound.
A linear programming relaxation of the generalized TSP problem can also be used to

0
(5.5)
This bound can be refined by adding some of the subtour constraints, which explicitly
forbid solutions that consist of disconnected cycles. Potentially, there are an exponential
number of subtour constraints, but in practice a small number of subtour constraints,
added in an iterative manner, will lead to good approximations of the value of the TSP
tour. The bound obtained in this way is referred to as the Held–Karp bound. In [23] it is
shown that for a wide variety of randomly generated instances, the cost of the optimal tour
is on average less than 0.8% of the Held–Karp bound, and for real-world instances the gap
is almost always less than 2%. A version of this approach to the TSP bound was imple-
mented by Allen et al.; computational results are presented in [1].
The edge cover problem can also be analyzed using polyhedral methods, to yield a
family of explicit lower bounds (see [16]). One specific edge cover bound was used in
[19] to solve the “Philadelphia problem,” a benchmark problem from the early days of the
frequency assignment problem.
5.2.2 Tile Cover Bounds
Bounds derived from the TSP and its relaxations may not be very good if c
i
+ c
j
< c
k
for
some indices i, j, k such that i + j
Ն
k. In this case, a piece of the tour consisting of
three consecutive nodes u, v, w so that d(u, v) = i, d(v, w) = j, and d(u, w) = k will con-
5.2 LOWER BOUNDS
101
tribute an amount of c

the same assignment will be repeated.
The cost of a tile cover y is defined as c(y) = ⌺
t
ʦ
T
y(t)c(t). The minimal cost of a tile
cover of a weighted, constrained graph (G, w) will be denoted by
␶
(G, w). In order to de-
rive lower bounds from tile covers, it must be established that for the graphs and con-
straints under consideration
S(G, w) Ն
␶
(G, w) – k
where k is a constant that does not depend on w.
The problem of finding a minimum cost tile cover of (G, w) can be formulated as an in-
teger program (IP) of the following form:
Minimize ⌺
t
ʦ
T
c(t)y(t) subject to:
⌺
t
ʦ
T
t(v)y(t) Ն w(v)(v ʦ V)
y(t) Ն 0(t ʦ T )
y integer
The linear programming (LP) relaxation of this IP is obtained by removing the require-

1
were considered. In this case the
channel assignment was found to be equivalent to the tile cover problem. Moreover, the
fractional tile cover problem is equivalent to the integral tile cover problem for 1-cliques,
leading to a family of lower bounds that can always be attained. None of the bounds was
new. Two bounds were clique bounds of the type mentioned earlier. The third bound was
first given by Gamst in [12], and can be stated as follows:
S(G, w) Ն max{c
0
w(v) + (
␮
c
1
– c
0
)w(C – v) – c
0
|C a clique of G, v ʦ C} (5.6)
where
␮
is such that (
␮
– 1)c
1
< c
0
Յ
␮
c
1

with node partition (Q, R) with constraints (k, u, a), every pair of nodes from Q has a con-
straint of at least u, while the constraint between any pair of nodes in the nested clique is at
least a.
The following is a lower bound for a nested clique (Q, R) with parameters (k, a, u):
S(G, w) Ն a
Α
vʦQ
w(v) + u
Α
vʦR
w(v) – u (5.7)
This bound was first derived in [12] using ad-hoc methods. The same bound can also be
derived using edge covers.
Using tile covers, a number of new bounds for nested cliques with parameters (k, u,1)
are obtained in [22]. The following is a generalization of bound (5.6). (The notation w
Qmax
and w
Rmax
is used to denote the maximum weight of any node in Q and R, respectively.)
S(G, w) Ն (k –
␮␦
)w
Qmax
+
␦
Α
vʦQ
w(v) +
⑀
Α