Weighted n-coloring problem algorithms

views:

answers:

+3 Q:

Weighted n-coloring problem algorithms

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

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

I imagine simulated annealing could be useful in this circumstance.

Links to code packages would also be super useful so I don't have to rewrite the wheel!

Thanks!

+1 A:

A very handy python package for experimenting with graphs is NetworkX. If you prefer C++ there's also boost, but using graphs in boost will seem ridiculously clumsy after NetworkX.

Simulated annealing isn't a bad idea. You can do a regular coloring first to find a lower bound which will help direct your search. You should define your problem more precisely, though. Do you mean to pick some pivot value for the sum of incoming edges and try to partition the colors around the pivot?

Ben Jackson 2010-10-19 20:34:14

Thanks for the recommendation - I'll check it out! I don't think I'm trying to pivot around a value for the sum. I'm trying to absolutely maximize the sum.Basically, the quality of a coloring equals the sum of the edges between vertices that have been colored the same. I'm trying to maximize the quality of the coloring.

Daniel Demetri 2010-10-20 14:03:30

Normally in a http://en.wikipedia.org/wiki/Graph_coloring there would be no "edges between vertices that have been colored the same". Do you mean you want to maximize the weights of edges *touching* vertices of the same color?

Ben Jackson 2010-10-20 16:12:43

No, in this case the graph is complete, so there are edges between each vertex and all over verticies. You're right that I'm re-interpreting the traditional "Graph Coloring" problem in which the adjacency list has binary values (edge exists or does not exist). In this case, the edges are integers and represent the cost or benefit of coloring the vertices the same.

Daniel Demetri 2010-10-25 01:41:54

ansaurus

tags:

views:

answers:

Weighted n-coloring problem algorithms

related questions