Return to results
Journal articles (2015), Discrete Applied Mathematics, 182, pp. 46-60

Directed weighted improper coloring for cellular channel allocation

ARCHETTI Claudia , Bianchessi Nicola, Hertz Alain, Colombet Adrien, Gagnon François

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. Link to the 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.

Keywords : #Graph-coloring, #Weighted-directed-graphs, #Channel-assignment, #Set-partitioning-formulations, #Branch, #and, #price-algorithm