CODEWITHSUNDEEP
algorithmgraphgenetic-algorithmheuristicstabu-search
user1544745
user1544745

Reputation: 697

State-of-the art graph coloring metaheuristics

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.

Upvotes: 4

Views: 877

Answers (2)

twistedlogic
twistedlogic

Reputation: 1

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.

Upvotes: 0

Geoffrey De Smet
Geoffrey De Smet

Reputation: 27312

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.

Upvotes: 1

Related Questions