# Coloring of nodes in a sensor networks

I have weighted graph for sensor networks with aggregation nodes and sensors. There is a edge between two nodes associated with a weight. Higher the weight, stronger the interference between the aggregation nodes if they have same color.

I need to perform graph coloring of these nodes with just K colors. The nodes with higher edge weight should/must have different colors.

What is an efficient way to do the optimal coloring?

Ideas:

May be the coloring of such a big network is too difficult. Instead we can have clusters of nodes and then do the intra-cluster coloring. But then we need to take care of inter-cluster interference.

I recommend first trying to solve the problem directly. For each edge $$(i,j)$$, let $$c_{ij}$$ be the edge weight. Let binary decision variable $$x_{ik}$$ indicate whether node $$i$$ is assigned color $$k$$. The problem is to minimize $$\sum_{i,j} c_{ij} \sum_k x_{ik} x_{jk}$$ subject to $$\sum_k x_{ik} = 1$$ for all $$i$$. You can call an MIQP solver or linearize the quadratic objective. To linearize, for each edge $$(i,j)$$ with $$c_{ij}>0$$, introduce binary (or just nonnegative) decision variable $$y_{ij}$$ to represent $$\sum_k x_{ik} x_{jk}$$, impose additional constraints $$y_{ij} \ge x_{ik} + x_{jk} - 1$$, and minimize $$\sum_{i,j} c_{ij} y_{ij}$$.
• you can see that there are large number of nodes. As it is clear from the problem description that one node will more more likely 5 to 6 nodes, i.e., most of $c_{i,j}$ are zero. How to take this into consideration o make the problem smaller/simpler?
• I would not be surprised if this problem can be solved quickly for a sparse graph with 500 nodes. You do not need $y_{ij}$ or its constraint if $c_{ij}=0$. I'll update my answer. Apr 13, 2023 at 13:54
• the second constraint can be expressed as: for $c=1:C$, for $i=1:N-1$, for $j=i+1:N$, if $w_{ij}>0$ $y_{ij}\ge x_{ic}+x_{jc}-1$, end if, end for, end for, end for. Am I right?
• Yes, this model allows such improper colorings. For edge $(i,j)$, if nodes $i$ and $j$ are assigned the same color $k$, then $x_{ik}=x_{jk}=1$, the constraints enforce $y_{ij}=1$, and the weight $c_{ij}$ is accrued. May 11, 2023 at 12:56