I have the same graph coloring problem as in

Coloring of nodes of a sensor network

@RobPratt and @prubin have proposed some very good solutions.

This time I am or interested in distributed coloring schemes considering the large size of the graph. I have around 3000-4000 nodes.

The problem remains the same....[copied from @RobPratt's answer]

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$.

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}$.

I am looking for a fully distributed solution. at any epoch, one node can talk or share info with only its neighbors.

The node can take color randomly in the very beginning. Ho do we proceed from there?

  • $\begingroup$ what exactly is your question? $\endgroup$
    – Kuifje
    Oct 2, 2023 at 9:47
  • $\begingroup$ @Kuifje I am looking for a distributed solution for this problem. $\endgroup$
    – KGM
    Oct 2, 2023 at 10:16
  • $\begingroup$ 3000-4000 nodes is not that big. You can get good solution in a few seconds without any distributed algorithm $\endgroup$
    – fontanf
    Oct 2, 2023 at 11:45
  • $\begingroup$ @fontanf would you please refer me to some solution for my problem which can be solved in just few seconds. $\endgroup$
    – KGM
    Oct 2, 2023 at 13:16
  • $\begingroup$ @fontanf some of the DIMACS coloring problems with approx 100 nodes cannot be solved optimally $\endgroup$
    – Kuifje
    Oct 2, 2023 at 13:39


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.