کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418188 | 681617 | 2015 | 15 صفحه PDF | دانلود رایگان |
Given a directed graph with weights on the vertices and on the arcs, a θθ-improper kk-coloring is an assignment of at most kk different colors to the vertices of GG such that the weight of every vertex vv is greater, by a given factor 1θ, than the sum of the weights on the arcs (u,v)(u,v) entering vv with the tail uu of the same color as vv. For a given real number θθ, we consider the problem of determining the minimum integer kk such that GG has a θθ-improper kk-coloring. Also, for a given integer kk, we consider the problem of determining the minimum real number θθ such that GG has a θθ-improper kk-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.
Journal: Discrete Applied Mathematics - Volume 182, 19 February 2015, Pages 46–60