Weighted n-coloring problem algorithms

Question

I have 100 vertices and a function f (x, y) that calculates the weight of an edge between vertex x and vertex y. f is not particularly expensive, so I could create an index adjacency list with weights if necessary.

What are some effective, acceptable methods for optimizing the n-coloring of these vertices by minimizing or maximizing the sum of the weights of all the edges connecting the vertices of the same color?

I suggest that simulated annealing may be useful in this case.

Links to code packages will also be very useful, so I don’t need to rewrite the wheel!

Thanks!

Answer 1

A very handy python package for experimenting with NetworkX graphics. If you prefer C ++, there is also a rise there, but using graphs in boost will seem like a ridiculous inconvenience after NetworkX.

Simulated annealing is a good idea. You can do the usual coloring first to find the bottom border that will help guide your search. However, you must define your problem more precisely. You mean, to select some rotation value by the sum of the incoming edges and try to separate the colors around the axis?