# Directed weighted improper coloring for cellular channel allocation

Given a directed graph with weights on the vertices and on the arcs, a -improper -coloring is an assignment of at most different colors to the vertices of such that the weight of every vertex is greater, by a given factor , than the sum of the weights on the arcs entering with the tail of the same color as . For a given real number , we consider the problem of determining the minimum integer such that has a -improper -coloring. Also, for a given integer , we consider the problem of determining the minimum real number such that has a -improper -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. Lien vers l'article

ARCHETTI, C., BIANCHESSI, N., HERTZ, A., COLOMBET, A. and GAGNON, F. (2015). Directed weighted improper coloring for cellular channel allocation. *Discrete Applied Mathematics*, 182, pp. 46-60.

Mots clés : #Graph-coloring, #Weighted-directed-graphs, #Channel-assignment, #Set-partitioning-formulations, #Branch, #and, #price-algorithm