Efficient channel assignment techniques in mobile cellular networks

A cellular network is often modeled as a graph and the Channel Assignment Problem is formulated as a coloring problem of the graph. The channel assignment algorithms partition the given radio spectrum into a set of disjoint channels that can be used simultaneously by the stations while maintaining acceptable radio signals. While in the classical vertex coloring problem a condition is imposed only on colors of adjacent nodes, many generalizations require colors to respect a stronger condition, e.g. restrictions are imposed on colors both of adjacent nodes and of nodes at distance 2 in the graph. This paper will focus on a specific graph coloring generalization that arose first from a channel assignment problem in radio networks: the L(h, k)-labeling problem. The aim of the L(h, k)-labeling problem is to minimize the span λh,k(G), i.e. the difference between the largest and the smallest used colors. The minimum span over all possible labeling functions is denoted by λh,k(G) and is called λh,k -number of G.