3

I have a graph coloring problem that involves thousands of vertices that have 10 to 50 edges each. I have been investigating many graph coloring heuristics (GA, tabu search...), but I find them difficult to compare and to decide which would suit me the best. Does anyone have any experience with large scale graph coloring to recomend a technique or to inform me about current state-or-the art algorithms in this domain?

Thanks.

user1544745
  • 677
  • 2
  • 8
  • 15

2 Answers2

1

Implement it in a optimization engine like Drools Planner and run it's benchmarker to figure out which metaheuristics work best.

Especially if you don't have a pure graph coloring problem (so you have extra constraints), it's impossible to tell in advance which metaheuristic will work best.

Geoffrey De Smet
  • 26,223
  • 11
  • 73
  • 120
0

A good solution that I know of is to use Simulated Annealing with Kempe chains. Basically, you use standard simulated annealing and when you want to do a random change to solution you pick two neighbouring nodes and you chage their color according to Kempe chains rule.

twistedlogic
  • 1
  • can you please add more details about `Kempe chains` – arunmoezhi Apr 25 '14 at 08:08
  • Well, I learned about this technic from prof. Pascal van Hentenryck course on Discrete optimization on Coursera. – twistedlogic Apr 26 '14 at 18:09
  • New offering of the course is available, I would recommend it. Kempe Chains Idea is the following : you want to change colour of one of the nodes to arbitrary colour but you also want to maintain feasibility of solution. For example you want to change colour of node n1 from blue to red. But you have two adjacent nodes to node n1, lets say n2 and n3 that are already red. Idea is to change colour on n1 from blue->red, n2 and n3 change red->blue, adj. red nodes to n2, n3 red->blue, and so on. This way feasibility of solution is maintained. – twistedlogic Apr 26 '14 at 18:27