### G-2012-85

# Directed Weighted Improper Coloring for Cellular Channel Allocation

## Claudia Archetti, Nicola Bianchessi, Alain Hertz, A Colombet, and François Gagnon

Given a directed graph with weights on the vertices and on the arcs, a θ-improper *k*-coloring is an assignment of at most *k* different colors to the vertices of *G* such that the weight of every vertex *v* is greater, by a factor 1/θ, than the sum of the weights on the arcs *(u,v)* entering *v* with the head *u* of the same color as *v*. For a given real number θ, we consider the problem of determining the minimum integer *k* such that *G* has a θ-improper *k*-coloring. Also, for a given integer *k*, we consider the problem of determining the minimum real number θ such that *G* has a θ-improper *k*-coloring. We show that these two problems can be used to model channel allocation problems in wireless communication networks, when it is required that the power of the signal received at a base station is greater, by a given factor, than the sum of interfering powers received from mobiles which are assigned the same channel. We propose set partitioning formulations for both problems and describe branch-and-price algorithms to solve them. Computational experiments are reported for instances having a similar structure as real channel allocation problems.

Published **December 2012**
,
22 pages