Archived

This topic is now archived and is closed to further replies.

_DarkWIng_

Optimizing graph vertex coloring

Recommended Posts

Hi! I have a bit of a problem with coloring graph vertices. All "standard" algoritem I found (and I understand) use uncolored graph for start, but I need something that starts on partly colored graph (some vertices have fixed color) and need to color the rest of graph. I know how to do this to find minimal coloring but that's O(n!) -> not realy useful. Greedy algo. also works but coloring is not so good(usualy produces 2x-3x more colors than minimal count). I was hoping for something that works in about O(n^3) and gives about ~1.5x colors... Any ideas? [edit] : @moderator : if this is not the right forum to ask please move it somewhere... You should never let your fears become the boundaries of your dreams. [edited by - _DarkWIng_ on May 3, 2003 1:16:50 PM]

Share this post


Link to post
Share on other sites
This could be the right forum, since the answer may be a math-optimized algorithm. But I don''t really understand the problem. What do you mean by a colored graph exactly? There are different ways to interpret.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Share this post


Link to post
Share on other sites
Something simmilar to minimal colored graph(exact solution is NP) using heuristic algo that starts on partly colored graph. I don''t realy know how to explain this very well.

You should never let your fears become the boundaries of your dreams.

Share this post


Link to post
Share on other sites
Have you tried doing greedy, but always choosing most constrained or least constrained? Also, you may want to try hill-climbing with random restart or simulated annealing.

Share this post


Link to post
Share on other sites