Directed weighted improper coloring for cellular channel allocation
Given a directed graph with weights on the vertices and on the arcs, a ? ? -improper k k -coloring is an assignment of at most k k different colors to the vertices of G G such that the weight of every vertex v v is greater, by a given factor 1 ? , than the sum of the weights on the arcs (u,v) ( u , v ) entering v v with the tail u u of the same color as v v . For a given real number ? ? , we consider the problem of determining the minimum integer k k such that G G has a ? ? -improper k k -coloring. Also, for a given integer k k , we consider the problem of determining the minimum real number ? ? such that G G has a ? ? -improper k 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.
set partitioning formulations branch-and-price algorithm graph coloring weighted directed graphs channel assignment