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 given factor 1θ, than the sum of the weights on the arcs (u,v) entering v with the tail 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.
Directed weighted improper coloring for cellular channel allocation / C. Archetti, N. Bianchessi, A. Hertz, A. Colombet, F. Gagnon. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - 182(2015), pp. 46-60.
|Titolo:||Directed weighted improper coloring for cellular channel allocation|
|Parole Chiave:||Graph coloring; Weighted directed graphs; Channel assignment; Set partitioning formulations; Branch-and-price algorithm;|
|Settore Scientifico Disciplinare:||Settore MAT/09 - Ricerca Operativa|
|Data di pubblicazione:||2015|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.1016/j.dam.2013.11.018|
|Appare nelle tipologie:||01 - Articolo su periodico|
File in questo prodotto:
|Directed-weighted-improper-coloring-for-cellular-channel-allocation_DAM-2015.pdf||Publisher's version/PDF||Open Access Visualizza/Apri|
|DWICP-revision2.pdf||Post-print, accepted manuscript ecc. (versione accettata dall'editore)||Open Access Visualizza/Apri|