Data di Pubblicazione:
2015
Citazione:
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]
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.
Tipologia IRIS:
01 - Articolo su periodico
Keywords:
Graph coloring; Weighted directed graphs; Channel assignment; Set partitioning formulations; Branch-and-price algorithm;
Elenco autori:
C. Archetti, N. Bianchessi, A. Hertz, A. Colombet, F. Gagnon
Link alla scheda completa: