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. [10.1016/j.dam.2013.11.018]
Directed weighted improper coloring for cellular channel allocation
N. Bianchessi;
2015
Abstract
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.File | Dimensione | Formato | |
---|---|---|---|
Directed-weighted-improper-coloring-for-cellular-channel-allocation_DAM-2015.pdf
accesso aperto
Tipologia:
Publisher's version/PDF
Dimensione
775.44 kB
Formato
Adobe PDF
|
775.44 kB | Adobe PDF | Visualizza/Apri |
DWICP-revision2.pdf
accesso aperto
Tipologia:
Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione
363.09 kB
Formato
Adobe PDF
|
363.09 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.